实现堆排序的C++程序

2023-06-20 22:56:03 75

堆是一个完整的二叉树，它要么是最小堆，要么是最大堆。在最大堆中，根处的键必须是堆中所有键中的最大值。对于该二叉树中的所有节点，此属性必须递归为真。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

实现堆排序的C++程序

功能说明

示例

热门推荐

随机推荐