数据结构之堆(Heap)

发表于 | 分类于

堆(Heap)

堆（heap）也被称为优先队列（priority queue）。队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。而堆也是一样，在堆底插入元素（并不是直接插到堆底完事，而是从堆底往上浮到对应的位置）在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。这个优先顺序可以是元素的大小或者其他规则。

堆可以看成一个二叉树，所以可以考虑使用二叉树的表示方法来表示堆。但是因为堆中元素按照一定的优先顺序排列，因此可以使用更简单的方法：数组，来表示，这样可以节省子节点指针空间，并且可以快速访问每个节点。

下面以最小堆为例，给出了一些堆的基本操作的伪代码，便于理解各项操作原理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*A是数组，假设数组的index从1开始而非从0开始*/

//i是堆顶的index,维护堆，基于i以下已经是最小堆的假设
//时间复杂度为O(logn)
MIN-HEAPIFY(A,i):
    l = i*2;        //左儿子
    r = i*2+1;      //右儿子
    small = i;
    if(l <= A.size() && l < A[i]):
        small = l;
    if(r <= A.size() && r < A[i]):
        small = r;
    if(small != i):
        swap(A[i],A[small]);
        MIN-HEAPIFY(A,small);

//取出最小堆中的最小元素,为保证结构，取出后将堆中的最后一个元素置于堆顶，然后下沉
//时间复杂度为O(logn)
HEAP-EXTRACT-MIN(A):
    if(A.size() < 1):
        error;
    min = A[1];
    A[1] = A[A.size()];
    A.size -= 1;
    MIN-HEAPIFY(A,1);
    return min;

//向堆中插入元素,先将元素置于底部，然后进行上浮
//时间复杂度为O(logn)
MIN-HEAP-INSERT(A,key):
    A.size() += 1;
    A[A.size()] = key;
    i = A.size();
    // 上浮，i/2为i的父节点
    while(i > 1 and A[i/2] > A[i]):
        swap(A[i/2],A[i]);
        i = i/2;

//c从数组构造堆,思想是从第一个非叶子节点起，对于每个节点维护堆
//可以证明，构建堆的时间复杂度为O(n),而非O(nlogn)
BUILD-MIN-HEAP(A):
    for(i = A.size/2; i >= 1; i--):
        MIN-HEAPIFY(A,i);

//从小到大的堆排序,思想是构造一个最大堆，每次将堆顶元素与堆的最后一项交换位置
//将堆的大小减一，往复操作，得到从小到大的数组
//时间复杂度为O(nlogn)
HEAP-SORT(A):
    BUILD-MAX-HEAP(A);
    for(i = A.size(); i>=2; i--):
        swap(A[i],A[1]);
        A.size -= 1;
        MAX-HEAPIFY(A,1);