กองเรียง

ดำเนินการเรียงลำดับฮีปบนโครงสร้างข้อมูลฮีป เรารู้ว่าฮีปเป็นต้นไม้ไบนารีที่สมบูรณ์ ต้นไม้กองสามารถเป็นสองประเภท ฮีปขั้นต่ำหรือฮีปสูงสุด สำหรับฮีปขั้นต่ำ องค์ประกอบรูทจะน้อยที่สุด และสำหรับฮีปสูงสุด รูทจะสูงสุด หลังจากสร้างฮีปแล้ว เราสามารถลบองค์ประกอบออกจากรูท และส่งองค์ประกอบสุดท้ายไปที่รูท หลังจากขั้นตอนการสลับเหล่านี้ เราจำเป็นต้องฮีปทั้งอาร์เรย์อีกครั้ง การลบองค์ประกอบออกจากรูททำให้เราสามารถจัดเรียงทั้งอาร์เรย์ได้

ความซับซ้อนของเทคนิค Heap Sort

• ความซับซ้อนของเวลา: O(n บันทึก n)
• ความซับซ้อนของอวกาศ: O(1)

อินพุตและเอาต์พุต

Input:
A list of unsorted data: 30 8 99 11 24 39
Output:
Array before Sorting: 30 8 99 11 24 39
Array after Sorting: 8 11 24 30 39 99

อัลกอริทึม

เฮปฟาย (อาร์เรย์, ขนาด)

อินพุต - อาร์เรย์ของข้อมูลและจำนวนทั้งหมดในอาร์เรย์

ผลลัพธ์ − ฮีปสูงสุดโดยใช้องค์ประกอบอาร์เรย์

Begin
   for i := 1 to size do
      node := i
      par := floor (node / 2)
      while par >= 1 do
         if array[par] < array[node] then
            swap array[par] with array[node]
         node := par
         par := floor (node / 2)
      done
   done
End

heapSort(อาร์เรย์, ขนาด)

อินพุต: อาร์เรย์ของข้อมูลและจำนวนทั้งหมดในอาร์เรย์

เอาต์พุต −nbsp; เรียงลำดับ

Begin
   for i := n to 1 decrease by 1 do
      heapify(array, i)
      swap array[1] with array[i]
   done
End

ตัวอย่าง

#include<iostream>
using namespace std;

void display(int *array, int size) {
   for(int i = 1; i<=size; i++)
      cout << array[i] << " ";
   cout << endl;
}

void heapify(int *array, int n) {
   int i, par, l, r, node;
   // create max heap

   for(i = 1; i<= n; i++) {
      node = i; par = (int)node/2;
      while(par >= 1) {
         //if new node bigger than parent, then swap
         if(array[par] < array[node])
            swap(array[par], array[node]);
         node = par;
         par = (int)node/2;//update parent to check
      }
   }
}

void heapSort(int *array, int n) {
   int i;

   for(i = n; i>= 1; i--) {
      heapify(array, i);//heapify each time
      swap(array[1], array[i]);//swap last element with first
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n+1]; //effective index starts from i = 1.
   cout << "Enter elements:" << endl;

   for(int i = 1; i<=n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   heapSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

ผลลัพธ์

Enter the number of elements: 6
Enter elements:
30 8 99 11 24 39
Array before Sorting: 30 8 99 11 24 39
Array after Sorting: 8 11 24 30 39 99