堆积

易经学习

天地变化的道理

分类目录

使用率很高网站

文章列表

生活要常常分享

维基百科

您身边百科全书

产品秀秀

免费为您秀产品

堆积

堆积堆（-- ）是计算机科学中的一种特别的完全二叉树。若是满足以下特性，即可称为堆积：「给定堆积中任意节点P和C，若P是C的母节点，那么P的值会小于等于（或大于等于）C的值」。若母节点的值恒小于等于子节点的值，此堆积称为最小堆积（-- ）；反之，若母节点的值恒大于等于子节点的值，此堆积称为最大堆积（-- ）。在堆积中最顶端的那一个节点，称作根节点（-- ），根节点本身没有母节点（-- 堆积始于在1964年发表的堆积排序（-- ），当时他提出了二元堆积树作为此演算法的资料结构。性质. 堆的实现通过构造二叉堆（binary heap），实为二叉树的一种；由于其应用的普遍性，当不加限定时，均指该数据结构的这种实现。这种数据结构具有以下性质。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。堆有许多种进阶类型包含了适合制作双端伫列的最大—最小堆积及制作优先权伫列的斐波那契堆积等。支持的基本操作. 某些堆实现还支持其他的一些操作，如斐波那契堆支持检查一个堆中是否存在某个元素。示例代码. 为将元素X插入堆中，找到空闲位置，建立一个空穴，若满足堆序性（英文：heap order），则插入完成；否则将父节点元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做上滤（percolate up）。 void Insert( ElementType X, PriorityQueue H ) { int i; if (IsFull(H)) { printf("Queue is full.\n"); return; for (i = ++H->Size; H->Element[i / 2] > X; i /= 2) H->Elements[i] = H->Elements[i / 2]; H->Elements[i] = X; 以上是插入到一个二叉堆的过程。 codice_1，删除最小元，即二叉树的根或父节点。删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。 ElementType DeleteMin(PriorityQueue H) { int i, Child; ElementType MinElement, LastElement; if (IsEmpty(H)) { printf("Queue is empty.\n"); return H->Elements[0]; MinElement = H->Elements[1]; LastElement = H->Elements[H->Size--]; for (i = 1; i * 2 Size; i = Child) { // Find smaller child. Child = i * 2; if (Child != H->Size && H->Elements[Child + 1] Elements[Child]) Child++; // Percolate one level. if (LastElement > H->Elements[Child]) H->Elements[i] = H->Elements[Child]; else break; H->Elements[i] = LastElement; return MinElement; 应用. 堆排序. 堆（通常是二叉堆）常用于排序。这种算法称作堆排序。事件模拟. 主要运用堆的排序以选择优先。优先权伫列. 在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的最佳数据结构。戴克斯特拉演算法. 在戴克斯特拉演算法中使用斐波那契堆积或二元堆可使得伫列的操作更为快速。

唐骏

八卦

杨成武

中华人民共和国行政区划

平原省

上校

印度尼西亚总统

武烈天皇

马力 (1952年)

知识管理

张艺谋

禅宗