– Heaps, Priority_queue, Huffman TreeComplete Binary Tree Example Maximum and Minimum Heaps Example Heap Insertion Example pushHeap() Example popHeap() Example Adjusting popHeap() Example Heapifying Example Heap Sort Example

Lecture 12

Huffman Tree

1

Main Index

Contents

Example of Complete Binary Tree for a Vector5

v[0]1 3

v[1]9 6 2

v[2]4

v[3]7 0 8

v[4]

v[5]

v[6]

v[7]2

v[8]

v[9]Main Index Contents

Maximum and Minimum Heaps Example55 40 50 52 15 30

25

10

11

5

10

20

22

(A) M aximum Heap (9 nodes)5

(B) M aximum Heap (4 nodes)10

10

50

15

30

11

20

52

55

40

25

22

(C) M inimum Heap (9 nodes)

(D) M inimum Heap (4 nodes)Contents

3

Main Index

Example of Heap Before and After Insertion of 5063 63

v[0]30 40 30

v[0]40

v[1]10 25 8

v[2]38 10

v[1]25 8

v[2]38

v[3]5 3 18

v[4]

v[5]

v[6]5

v[3]3 18

v[4]50

v[5]

v[6]

v[7]

v[8]

v[9] (a)

v[7]

v[8]

v[9]

v[10] (b)

4

Main Index

Contents

Example of Reorder the tree in pushHeap()63 63 63

v[0]30

... ...25

v[0]50

... ...25

v[0]50

...

v[1]50

v[1]30

...

v[1]30

v[4]18 18

v[4]18

v[4]25

v[9]

v[10]

v[9]

v[10]

v[9]

v[10]

Step 1 Compare 50 and 25 (Exchange v[10] and v[4])

Step 2 Compare 50 and 30 (Exchange v[4] and v[1])Main Index Contents

Step 3 Compare 50 and 63 (50 in correct location)

pushHeaptemplate <typename T, typename Compare> void pushHeap(vector<T>& v, int last, Compare comp) //compare为”>”,得到的堆是最大堆，否则是最小堆 { int currentPos, parentPos; T target; currentPos = last-1; parentPos = (currentPos-1)/2; target = v[last-1]; while (currentPos != 0) { if (comp(target,v[parentPos])) //if true, 边交换边向上比较 { v[currentPos] = v[parentPos]; currentPos = parentPos; parentPos = (currentPos-1)/2; } else break; } v[currentPos] = target; } Main Index Contents

Example of Exchanging elements in popHeap()63 18

v[0]30 40 30

v[0]40

v[1]10 25 8

v[2]38 10

v[1]25 8

v[2]38

v[3]5 3 18

v[4]

v[5]

v[6]5

v[3]3 63

v[4]

v[5]

v[6]

v[7]

v[8]

v[9] Before a deletion

v[7]

v[8]

v[9] After exchanging the root and last element in the heap

7

Main Index

Contents

Example of Adjusting the heap for popHeap()

40

40

...

v[0]18

...38

v[0]38

v[2]8 8

v[2]18

v[5]

v[6]

v[5]

v[6]

Step 1: Exchange 18 and 408Main Index Contents

Step 2: Exchange 18 and 38

Pop--AdjustHeaptemplate <typename T, typename Compare> void adjustHeap(vector<T>& v, int first, int last, Compare comp)//”>” { int currentPos, childPos; T target; currentPos = first; target = v[first]; childPos = 2 * currentPos + 1; while (childPos <= last-1) { if ((childPos+1 <= last-1) && comp(v[childPos+1], v[childPos])) childPos = childPos + 1; if (comp(v[childPos],target)) { v[currentPos] = v[childPos]; currentPos = childPos; childPos = 2 * currentPos + 1; } else break; } v[currentPos] = target; Index Main Contents

pushHeap堆操作： 堆插入：pushHeap 新item插入到

向量尾部，自底向上比较，直到找到插入点； O(log2n) 堆删除：adjustHeap-popHeap 顶部元素与尾部元素互换，自顶向下比较，直到找到插入点； O(log2n)

建堆方法： 1.边比较边插入，使用pushHeap O(nlog2n) 2.先按层次顺序插入元素，形成完全二叉树，再从最后一个非叶子 节点依次向上调整，每个节点调整使用adjustHeap O(n/2*log2n)

10

Main Index

Contents

popHeaptemplate <typename T, typename Compare> void popHeap(vector<T>& v, int last, Compare comp) { T temp; temp = v[0]; v[0] = v[last-1]; v[last-1] = temp; adjustHeap(v, 0, last-1, comp); }

11

Main Index

Contents

Heap sort#include <iostream> #include <vector> #include "d_heap.h" #include "d_util.h" using namespace std; int main() { int arr[] = {5, 9, 2, 7, 1, 3, 8}; int i, arrSize = sizeof(arr)/sizeof(int); vector<int> vA, vB; for (i = 0; i < arrSize; i++) //建堆，边插入边建堆 { vA.push_back(arr[i]); pushHeap(vA, vA.size(), greater<int>()); //最大堆 vB.push_back(arr[i]); pushHeap(vB, vB.size(), less<int>()); //最小堆 } cout << "Maximum heap: ";

12

Main Index

Contents

Example of Implementing heap operationwhile (!vA.empty()) { popHeap(vA, vA.size(), greater<int>()); cout << vA.back() << " "; vA.pop_back(); } cout << endl; cout << "Minimum heap: "; while (!vB.empty()) { popHeap(vB, vB.size(), less<int>()); cout << vB.back() << " "; vB.pop_back(); } cout << endl; return 0; }

13

Main Index

Contents

堆序化(Heapified Tree)int arr[] = {50, 20, 75, 35, 25}; vector<int> v(arr, 5);75

35

50

20

25

Heapified Tree14Main Index Contents

Heapified TreeCalling popHeap() with last = 5 deletes 75 and stores it in h[4]50

Calling popHeap() with last = 4 deletes 50 and stores it in h[3]35

35

25

20

25

20

75

50

75

Calling popHeap() with last = 3 deletes 35 and stores it in h[2]25

Calling popHeap() with last = 2 deletes 25 and stores it in h[1]20

20

35

25

35

50

75

50

75

…… 此处隐藏：2494字，全部文档内容请下载后查看。喜欢就下载吧 ……