实现堆排序的C++程序
堆是一个完整的二叉树,它要么是最小堆,要么是最大堆。在最大堆中,根处的键必须是堆中所有键中的最大值。对于该二叉树中的所有节点,此属性必须递归为真。MinHeap类似于MinHeap。
功能说明
voidBHeap::Insert(intele):执行插入操作以在堆中插入元素。
voidBHeap::DeleteMin():执行删除操作从堆中删除最小值。
intBHeap::ExtractMin():从堆中提取最小值的执行操作。
voidBHeap::showHeap():显示堆的元素。
voidBHeap::heapifyup(intin):以自底向上的方式维护堆结构。
voidBHeap::heapifydown(intin):以自上而下的方式维护堆结构。
示例
#include输出结果#include #include #include using namespace std; class BHeap { private: vector 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"< >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"< ::iterator pos = heap.begin(); cout<<"Heap --> "; while (pos != heap.end()) { cout<<*pos<<" "; pos++; } cout< = 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