打开主菜单

堆積

計算機科學中一種樹狀資料結構

(英語:Heap)是计算机科学中的一種特別的樹狀数据结构。若是滿足以下特性,即可稱為堆積:「給定堆積中任意節點P和C,若P是C的母節點,那麼P的值會小於等於(或大於等於)C的值」。若母節點的值恆小於等於子節點的值,此堆積稱為最小堆積min heap);反之,若母節點的值恆大於等於子節點的值,此堆積稱為最大堆積max heap)。在堆積中最頂端的那一個節點,稱作根節點root node),根節點本身沒有母節點parent node)。

堆積始於J. W. J. Williams英语J. W. J. Williams在1964年發表的堆積排序heap sort),當時他提出了二元堆積樹作為此演算法的資料結構。堆積在戴克斯特拉演算法(英語:Dijkstra's algorithm)中亦為重要的關鍵。

队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。[1]

逻辑定义编辑

 个元素序列 ,当且仅当满足下列关系时称之为堆:

 

或是:

 

性质编辑

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆大根堆,根节点最小的堆叫做最小堆小根堆。常见的堆有二叉堆斐波那契堆等。

支持的基本操作编辑

操作 描述 时间复杂度
build 建立一个空堆  
insert 向堆中插入一个新元素  
update 将新元素提升使其符合堆的性质
get 获取当前堆顶元素的值  
delete 删除堆顶元素  
heapify 使删除堆顶元素的堆再次成为堆

某些堆实现还支持其他的一些操作,如斐波那契堆支持检查一个堆中是否存在某个元素。

例程编辑

为将元素X插入堆中,找到空闲位置,建立一个空穴,若满足堆序性(英文:heap order),则插入完成;否则将父节点元素装入空穴,删除该父节点元素,完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。[1]

 1 void Insert( ElementType X, PriorityQueue H ) {
 2     int i;
 3     if (IsFull(H)) {
 4         printf("Queue is full.\n");
 5         return;
 6     }
 7     for (i = ++H->Size; H->Element[i / 2] > X; i /= 2)
 8         H->Elements[i] = H->Elements[i / 2];
 9     H->Elements[i] = X;
10 }

以上是插入到一个二叉堆的过程。

DeleteMin,删除最小元,即二叉树的根或父节点。删除该节点元素后,队列最后一个元素必须移动到堆得某个位置,使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤

 1 ElementType DeleteMin(PriorityQueue H) {
 2     int i, Child;
 3     ElementType MinElement, LastElement;
 4     if (IsEmpty(H)) {
 5         printf("Queue is empty.\n");
 6         return H->Elements[0];
 7     }
 8     MinElement = H->Elements[1];
 9     LastElement = H->Elements[H->Size--];
10     for (i = 1; i * 2 <= H->Size; i = Child) {
11         // Find smaller child.
12         Child = i * 2;
13         if (Child != H->Size && H->Elements[Child + 1]
14                 <  H->Elements[Child])
15             Child++;
16         // Percolate one level.
17         if (LastElement > H->Elements[Child])
18             H->Elements[i] = H->Elements[Child];
19         else
20             break;
21     }
22     H->Elements[i] = LastElement;
23     return MinElement;
24 }

应用编辑

堆排序编辑

堆(通常是二叉堆)常用于排序。这种算法称作堆排序

事件模拟编辑

主要运用堆的排序以选择优先。

参考编辑

  1. ^ 1.0 1.1 《数据结构与算法分析》Mark Allen Weiss(美)第六章,优先队列(堆)。

参见编辑