简单大根堆的实现

 1 //头文件定义--heap.h
 2 #ifndef _MAXHEAP_H_
 3 #define _MAXHEAP_H_
 4 template<class T>
 5 class MaxHeap{
 6 public:
 7     MaxHeap(int size=10);
 8     virtual ~MaxHeap();
 9 
10     bool IsEmpty();
11     void Pop();
12     void Push(const T&);
13     const T& Top()const;
14 private:
15     int current_size;//堆的当前节点个数
16     int max_size;//设置堆的最大节点个数
17     T *heap_array;
18 
19     void TrickleUp(int index);//插入新节点（末尾），接着向上渗透
20     void TrickleDown(int index);//删除根节点（用最后一个节点补到根节点），接着向下渗透
21 };
22 #endif

 1 #include<iostream>
 2 using namespace std;
 3 #include"Heap.h"
 4 template<class T>
 5 MaxHeap<T>::MaxHeap(int size = 10)
 6 {
 7     if (size < 1)
 8         throw "max size must be >=1";
 9     max_size = size;
10     current_size = 0;
11     heap_array = new T[max_size];//int *a = new int[100];开辟一个大小为100的整型数组空间
12 }
13 
14 template<class T>
15 bool MaxHeap<T>::IsEmpty()
16 {
17     return current_size == 0;
18 }
19 
20 template<class T>
21 MaxHeap<T>::~MaxHeap()
22 {
23     delete[] heap_array;
24 }
25 
26 template<class T>
27 void MaxHeap<T>::Push(const T& e)
28 {
29     if (current_size == max_size) throw "max_array is full";
30     heap_array[current_size] = e;
31     TrickleUp(current_size++);
32 }
33 
34 template<class T>
35 void MaxHeap<T>::TrickleUp(int index)//向上渗透，将新插入的元素向上调整到合适的位置
36 {
37     T bottom = heap_array[index];
38     int parent = (index - 1) / 2;
39     while (index > 0 && heap_array[parent] < bottom)//注意这个地方自己第一次写成了heap_array[parent]<heap_array[index]
40     {
41         heap_array[index] = heap_array[parent];
42         index = parent;
43         parent = (parent - 1) / 2;
44     }
45     heap_array[index] = bottom;
46 }
47 
48 template<class T>
49 void MaxHeap<T>::Pop()
50 {
51     heap_array[0] = heap_array[--current_size];
52     TrickleDown(0);
53 }
54 
55 template<class T>
56 const T& MaxHeap<T>::Top()const
57 {
58     return heap_array[0];
59 }
60 
61 template<class T>
62 void MaxHeap<T>::TrickleDown(int index)//向下渗透，将当前位置的元素向下调整到合适位置，保持大根堆的性质
63 {
64     T top = heap_array[index];
65     int larger_child;
66     while (index < current_size / 2)//这是完全二叉树的性质（最后一个非叶子节点的位置索引），好好体会
67     {
68         int lchild = 2 * index + 1;
69         int rchild = 2 * (index + 1);
70         if (rchild < current_size && heap_array[lchild] < heap_array[rchild])
71             larger_child = rchild;
72         else larger_child = lchild;
73         if (top >= heap_array[index])//!!
74             break;
75         heap_array[index] = heap_array[larger_child];
76         index = larger_child;
77     }
78     heap_array[index] = top;//这一句我第一次写时遗漏了
79 }
80 
81 int main()
82 {
83     MaxHeap<int> heap(20);
84     cout << heap.IsEmpty() << endl;;
85     heap.Push(7);
86     heap.Push(24);
87     heap.Push(9);
88     cout << heap.Top() << endl;
89     heap.Push(25);
90     heap.Push(28);
91     cout << heap.Top() << endl;
92     heap.Pop();
93     heap.Pop();
94     cout << heap.Top() << endl;
95 
96     return 0;
97 }