堆是一个完整的二叉树,它要么是最小堆,要么是最大堆。在最大堆中,根处的键必须是堆中所有键中的最大值。对于该二叉树中的所有节点,此属性必须递归为真。Min Heap 类似于 MinHeap。
void BHeap:: Insert(int ele):执行插入操作以在堆中插入元素。
void BHeap:: DeleteMin():执行删除操作从堆中删除最小值。
int BHeap:: ExtractMin():从堆中提取最小值的执行操作。
void BHeap:: showHeap():显示堆的元素。
void BHeap:: heapifyup(int in):以自底向上的方式维护堆结构。
void BHeap:: heapifydown(int in):以自上而下的方式维护堆结构。
#include <iostream> #include <cstdlib> #include <vector> #include <iterator> using namespace std; class BHeap { private: vector <int> heap; int l(int parent); int r(int parent); int par(int child); void heapifyup(int in); void heapifydown(int in); public: BHeap() {} void Insert(int element); void DeleteMin(); int ExtractMin(); void showHeap(); int Size(); }; int main() { BHeap h; while (1) { cout<<"1.Insert Element"<<endl; cout<<"2.Delete Minimum Element"<<endl; cout<<"3.Extract Minimum Element"<<endl; cout<<"4.Show Heap"<<endl; cout<<"5.Exit"<<endl; int c, e; cout<<"输入您的选择: "; cin>>c; switch(c) { case 1: cout<<"输入要插入的元素: "; cin>>e; h.Insert(e); break; case 2: h.DeleteMin(); break; case 3: if (h.ExtractMin() == -1) { cout<<"Heap is Empty"<<endl; } else cout<<"最小元素: "<<h.ExtractMin()<<endl; break; case 4: cout<<"显示 Hwap 的元素: "; h.showHeap(); break; case 5: exit(1); default: cout<<"Enter Correct Choice"<<endl; } } return 0; } int BHeap::Size() //堆大小{ return heap.size(); } void BHeap::Insert(int ele) //在堆中插入元素{ heap.push_back(ele);//将元素推入堆 heapifyup(heap.size() -1);//调用 heapifyup() 来维护堆结构 } void BHeap::DeleteMin() //从堆中删除最小值{ if (heap.size() == 0) { cout<<"Heap is Empty"<<endl; return; } heap[0] = heap.at(heap.size() - 1); heap.pop_back();//流行元素 heapifydown(0); cout<<"Element Deleted"<<endl; } int BHeap::ExtractMin() //从堆中提取最小值 { if (heap.size() == 0) { return -1; } else return heap.front(); } void BHeap::showHeap() //显示堆的元素{ vector <int>::iterator pos = heap.begin(); cout<<"Heap --> "; while (pos != heap.end()) { cout<<*pos<<" "; pos++; } cout<<endl; } int BHeap::l(int parent) // 返回节点的左孩子。 { int l = 2 * parent + 1; if (l < heap.size()) return l; else return -1; } int BHeap::r(int parent) // 返回节点的右孩子。 { int r = 2 * parent + 2; if (r < heap.size()) return r; else return -1; } int BHeap::par(int child)// 返回父母 { int p = (child - 1)/2; if (child == 0) return -1; else return p; } void BHeap::heapifyup(int in)//以自下而上的方式维护堆结构。 { if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) { int temp = heap[in]; heap[in] = heap[par(in)]; heap[par(in)] = temp; heapifyup(par(in)); } } void BHeap::heapifydown(int in)//以自上而下的方式维护堆结构。 { int child = l(in); int child1 = r(in); if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) { child = child1; } if (child > 0 && heap[in] > heap[child]) { int t = heap[in]; heap[in] = heap[child]; heap[child] = t; heapifydown(child); } }输出结果
1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 1 输入要插入的元素: 2 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 1 输入要插入的元素: 3 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 1 输入要插入的元素: 7 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 1 输入要插入的元素: 6 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 4 显示 Hwap 的元素: Heap --> 2 3 7 6 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 3 最小元素: 2 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 3 最小元素: 2 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 2 Element Deleted 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 4 显示 Hwap 的元素: Heap --> 3 6 7 1.Insert Element 2.Delete Minimum Element 3.Extract Minimum Element 4.Show Heap 5.Exit 输入您的选择: 5