数据结构--堆

【1】什么是堆？

堆是一种特殊的完全二叉树（关于完全二叉树可以参见随笔《树》）。

堆分为两种：最大堆和最小堆

最大堆只需要满足父节点大于两个子节点，而子节点之间没有要求。

最小堆只需要满足父节点小于两个子节点，而子节点之间没有要求。

那么，既然作为一棵完全二叉树，每层中的节点应该是从左到右填满的。

如果一个节点没有左儿子，那么它一定也没有右儿子。

并且在第N层中如果存在节点，肯定是由左向右依次排列，而且第N-1层必须是填满的。

【2】堆的实现

最小堆的实现代码如下：

  1 #include <iostream>
  2 #include <assert.h>
  3 #include <windows.h>
  4 #include <time.h>
  5 #include <iomanip>
  6 using namespace std;
  7 
  8 template<typename Type>
  9 class  Heap
 10 {
 11 public:
 12     virtual bool Insert(const Type &x) = 0;
 13     virtual bool Remove(Type &x) = 0;
 14 };
 15 template<typename Type>
 16 class MinHeap
 17 {
 18 private:
 19     enum { DEFAULTSIZE = 10 };
 20     Type *heap;
 21     int  Cursize;
 22     int  Maxsize;
 23 private:
 24     void  FilterDown(const int pos,const int end);
 25     void  FilterUp(const int  start);
 26 public:
 27     MinHeap(int sz = DEFAULTSIZE);
 28     MinHeap(int ar[], int n);
 29     MinHeap(const  MinHeap<Type>  &mh);
 30     MinHeap<Type> & operator=(const  MinHeap<Type> &mh);
 31     ~MinHeap();
 32     bool Insert(const Type &x);
 33     bool Remove(Type &x);
 34     bool IsEmpty() const;
 35     bool IsFull() const;
 36     void MakeEmpty();
 37 public:
 38     template<class Type>
 39     friend ostream &operator<<(ostream  &out,MinHeap<Type> &mh);
 40 };
 41 
 42 template<typename  Type>
 43 MinHeap<Type>::MinHeap(int sz)
 44 {
 45     Maxsize = sz > DEFAULTSIZE ? sz : DEFAULTSIZE;
 46     heap = new  Type[Maxsize+1];
 47     assert(heap != NULL);
 48     memset(heap, 0, sizeof(Type) * (Maxsize+1));
 49     Cursize = 0;
 50 }
 51 template<typename  Type>
 52 MinHeap<Type>::MinHeap(int ar[], int n)
 53 {
 54     Cursize = Maxsize = n;
 55     heap = new Type[Maxsize+1];
 56     assert(heap != NULL);
 57     for (int i = 0; i < Maxsize; i++)
 58     {
 59         heap[i+1] = ar[i];
 60     }
 61     int pos = Cursize/2;
 62     while (pos > 0)
 63     {
 64         FilterDown(pos, Cursize);
 65         --pos;
 66     }
 67 }
 68 template<typename Type>
 69 MinHeap<Type>::MinHeap(const MinHeap<Type> &mh)
 70 {
 71     Cursize = mh.Cursize;
 72     Maxsize = mh.Maxsize;
 73     heap = new Type[Maxsize+1];
 74     assert(heap != NULL);
 75     memcpy(heap, mh.heap, sizeof(Type) * (Cursize+1));
 76 }
 77 template<typename Type>
 78 MinHeap<Type> & MinHeap<Type>::operator=(const MinHeap<Type> &mh)
 79 {
 80     if (this != &mh)
 81     {
 82         Cursize = mh.Cursize;
 83         Maxsize = mh.Maxsize;
 84         delete []heap;
 85         heap = new Type[Maxsize+1];
 86         assert(heap != NULL);
 87         memcpy(heap, mh.heap, sizeof(Type) * (Cursize+1));
 88     }
 89     return *this;
 90 }
 91 template<typename Type>
 92 MinHeap<Type>::~MinHeap()
 93 {
 94     if (heap != NULL)
 95     {
 96         delete []heap;
 97         heap = NULL;
 98     }
 99     Cursize = Maxsize = 0;
100 }
101 template<typename Type>
102 void MinHeap<Type>::FilterDown(const int pos, const int end)
103 {
104     int i = pos, j = i*2; // j是i的左子女
105     heap[0] = heap[i];
106     while (j <= end)
107     {
108         if (j < end && heap[j] > heap[j+1])    // 取孩子中大者
109         {
110             ++j;
111         }
112         if (heap[j] < heap[0])    // 父节点 大于 子女节点的最大者
113         {
114             heap[i] = heap[j]; // 对换
115             i = j;
116             j = i*2;
117         }
118         else
119         {
120             break;
121         }
122     }
123     heap[i] = heap[0];
124 }
125 template<typename Type>
126 void MinHeap<Type>::FilterUp(const int  start)
127 {
128     int i = start, j = i/2; // j是i的双亲
129     heap[0] = heap[i];
130     while (i > 1)
131     {
132         if (heap[j] > heap[0])
133         {
134             heap[i] = heap[j];
135             i = j;
136             j = i/2;
137         }
138         else
139         {
140             break;
141         }
142     }
143     heap[i] = heap[0];
144 }
145 template<typename Type>
146 bool MinHeap<Type>::Insert(const Type &x)
147 {
148     if (Cursize < Maxsize)
149     {
150         heap[++Cursize] = x;
151         FilterUp(Cursize);
152         return true;
153     }
154 
155     return  false;
156 }
157 template<typename Type>
158 bool MinHeap<Type>::Remove(Type &x)
159 {
160     if (Cursize > 0)
161     {
162         x = heap[1];
163         heap[1] = heap[Cursize--];
164         FilterDown(1, Cursize);
165         return true;
166     }
167 
168     return false;
169 }
170 template<typename Type>
171 bool MinHeap<Type>::IsEmpty() const
172 {
173     return  0 == Cursize;    
174 }
175 template<typename Type>
176 bool MinHeap<Type>::IsFull() const
177 {
178     return Cursize == Maxsize;
179 }
180 template<typename Type>
181 void MinHeap<Type>::MakeEmpty()
182 {
183     Cursize = 0;
184 }
185 template<typename  Type>
186 ostream & operator<<(ostream &out, MinHeap<Type> &mh)
187 {
188     while (!mh.IsEmpty())
189     {
190         int temp;
191         mh.Remove(temp);
192         out << temp << setw(5);
193     }
194     out << endl;
195     return out;
196 }

View Code

Good Good Study, Day Day Up.

顺序选择循环总结