Sắp xếp đống

Sắp xếp đống được thực hiện trên cấu trúc dữ liệu đống. Chúng ta biết rằng heap là một cây nhị phân hoàn chỉnh. Cây đống có thể có hai loại. Min-heap hoặc max heap. Đối với heap tối thiểu, phần tử gốc là tối thiểu và đối với heap tối đa, phần tử gốc là tối đa. Sau khi hình thành một đống, chúng ta có thể xóa một phần tử khỏi gốc và gửi phần tử cuối cùng đến gốc. Sau thủ tục hoán đổi này, chúng ta cần phải xếp chồng lại toàn bộ mảng. Bằng cách xóa các phần tử khỏi gốc, chúng ta có thể sắp xếp toàn bộ mảng.

Sự phức tạp của Kỹ thuật Sắp xếp Heap

• Độ phức tạp về thời gian: O (n log n)
• Mức độ phức tạp của không gian: O (1)

Đầu vào và Đầu ra

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

Thuật toán

heapify (mảng, kích thước)

Đầu vào - Một mảng dữ liệu và tổng số trong mảng

Đầu ra - Heap tối đa bằng cách sử dụng một phần tử mảng

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 (mảng, kích thước)

Đầu vào: Một mảng dữ liệu và tổng số trong mảng

Đầu ra −nbsp; mảng đã sắp xếp

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

Ví dụ

#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);
}

Đầu ra

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