โปรแกรม C++ เพื่อใช้ Heap Sort

Heap เป็นไบนารีทรีที่สมบูรณ์ซึ่งก็คือ Min Heap หรือ Max Heap ใน Max Heap คีย์ที่รูทจะต้องสูงสุดในบรรดาคีย์ทั้งหมดที่มีอยู่ใน Heap คุณสมบัตินี้ต้องเป็นจริงแบบเรียกซ้ำสำหรับโหนดทั้งหมดในทรีไบนารีนั้น Min Heap คล้ายกับ MinHeap

คำอธิบายฟังก์ชัน

โมฆะ BHeap::Insert(int ele): ดำเนินการแทรกเพื่อแทรกองค์ประกอบในฮีป

โมฆะ BHeap::DeleteMin(): ดำเนินการลบเพื่อลบค่าต่ำสุดจากฮีป

int BHeap::ExtractMin(): ดำเนินการเพื่อดึงค่าต่ำสุดจากฮีป

เป็นโมฆะ BHeap::showHeap(): เพื่อแสดงองค์ประกอบของฮีป

เป็นโมฆะ BHeap::heapifyup(int in): รักษาโครงสร้างฮีปแบบล่างขึ้นบน

เป็นโมฆะ 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<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter the element to be inserted: ";
            cin>>e;
            h.Insert(e);
            break;
         case 2:
            h.DeleteMin();
            break;
         case 3:
            if (h.ExtractMin() == -1) {
               cout<<"Heap is Empty"<<endl;
            }
            else
               cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
            break;
         case 4:
            cout<<"Displaying elements of Hwap: ";
            h.showHeap();
            break;
         case 5:
            exit(1);
         default:
            cout<<"Enter Correct Choice"<<endl;
      }  
   }
   return 0;
}
int BHeap::Size() //size of heap {
   return heap.size();
}
void BHeap::Insert(int ele) //insert element in heap {
   heap.push_back(ele);//push element into the heap
   heapifyup(heap.size() -1);//call heapifyup() to maintain heap structure
}
void BHeap::DeleteMin() //delete minimum value from heap {
   if (heap.size() == 0) {
      cout<<"Heap is Empty"<<endl;
      return;
   }
   heap[0] = heap.at(heap.size() - 1);
   heap.pop_back();//pop element
   heapifydown(0);
   cout<<"Element Deleted"<<endl;
}
int BHeap::ExtractMin() //extract minimum value from heap
{
   if (heap.size() == 0) {
      return -1;
   }
   else
      return heap.front();
}
void BHeap::showHeap() //show the elements of heap {
   vector <int>::iterator pos = heap.begin();
   cout<<"Heap --> ";
   while (pos != heap.end()) {
      cout<<*pos<<" ";
      pos++;
   }
   cout<<endl;
}
int BHeap::l(int parent) // return left child of node.
{
   int l = 2 * parent + 1;
   if (l < heap.size())
      return l;
   else
      return -1;
}
int BHeap::r(int parent) // return right child of node.
{
   int r = 2 * parent + 2;
   if (r < heap.size())
      return r;
   else
      return -1;
}
int BHeap::par(int child)// return parent
{
   int p = (child - 1)/2;
   if (child == 0)
      return -1;
   else
      return p;
}
void BHeap::heapifyup(int in)//maintain heap structure in bottom up manner.
{
   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)//maintain heap structure in top down manner.
{
   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
Enter your choice: 1
Enter the element to be inserted: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 3
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 7
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 1
Enter the element to be inserted: 6
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 2 3 7 6
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 3
Minimum Element: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 3
Minimum Element: 2
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 2
Element Deleted
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 4
Displaying elements of Hwap: Heap --> 3 6 7
1.Insert Element
2.Delete Minimum Element
3.Extract Minimum Element
4.Show Heap
5.Exit
Enter your choice: 5