heap

heap

heap:

(二叉)堆是一个数组，可以被看做完全二叉树，根结点是1，lch=2*pa,rch=2*pa+1。堆常有max_heap和min_heap，前者heap[parent]>=heap[child]，后者heap[parent]<=heap[child],最小堆常常用于构造优先队列，不断输入数据时需要维护堆的性质，比如max_heap中的max_heapify，如果输入的数据比孩子结点小，则让其逐级下降。

MAX-HEAPIFY (A, i )

1  l= LEFT (i)

2  r= RIGHT (i)

3  if l<=A. heap-size and A[l] > A[i]

4      largest = l

5  else largest = i

6  if r <=A. heap-size and A[r] > A[largest]

7      Largest = r

8  if larget !=i

9      exchange A[i] with  A[largest]

10     MAX-HEAPIFY(A, Largest )

时间复杂度：O(h).

建堆：

可以用自底向上的方法利用过程MAX-HEAPIFY把一个大小为n=A.length的数组 A[1..n]转换为最大堆。子数组A(n/2+1..n)中的元素都是树的叶 结点。每个叶结点都可以看成只包含一个元素的堆。过程BUILD-MAX-HEAP对树中的其他结 点都调用一次MAX-HEAPIFY.

BUILD-MAX-HEAP(A)

1 A. heap-size = A. length

2 for i = A. length/2--> 1

3     MAX-HEAPIFY(A, i)

最小堆构造类似。

堆排序（可参照《算法导论》）：

heapsort的时间复杂度：O(nlgn).

sort_heap，make_heap,pop_heap,push_heap是C++标准算法库里的模板函数，用于将存储在vector/deque 中的元素进行堆操作。利用vector::push_back配合push_heap把一个元素添加到堆中,利用vector::pop_back配合pop_heap把堆定元素删除。

例如：

#include #include#include#includeusing namespace std;vector vec;void show(){ vector::iterator ix=vec.begin(); for(;ix()); cout<<"minheap: "; show(); sort_heap(vec.begin(),vec.end()); cout<<"sorted: "; show(); make_heap(vec.begin(),vec.end(),less()); cout<<"maxheap: "; show(); pop_heap(vec.begin(),vec.end());//pop_heap之后堆顶元素放到最后搁着，1--last-1元素形成新的堆 cout<<"pop_heap:\n"; cout<<"(1):"; show();//pop_heap与vec.pop_back合用删除堆顶元素。 vec.pop_back(); cout<<"(2):"; show(); vec.push_back(15); push_heap(vec.begin(),vec.end()); //加入新的元素后构造新堆 show(); return 0;}

输出：

5 3 9 6 10 16 1

minheap: 1 3 5 6 10 16 9

sorted:  3 6 9 10 16 5 1

maxheap: 16 10 9 3 6 5 1

pop_heap:

(1):10 6 9 3 1 5 16

(2):10 6 9 3 1 5

15 6 10 3 1 5 9

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。