ढेर बनाएं और छांटें

हीप डेटा संरचना पर हीप सॉर्ट किया जाता है। हम जानते हैं कि ढेर एक पूर्ण बाइनरी ट्री है। हीप ट्री दो प्रकार का हो सकता है। न्यूनतम ढेर या अधिकतम ढेर। न्यूनतम ढेर के लिए मूल तत्व न्यूनतम है और अधिकतम ढेर के लिए जड़ अधिकतम है। ढेर बनाने के बाद, हम एक तत्व को जड़ से हटा सकते हैं और अंतिम तत्व को जड़ में भेज सकते हैं। इन स्वैपिंग प्रक्रिया के बाद, हमें पूरे सरणी को फिर से ढेर करना होगा। तत्वों को रूट से हटाकर हम पूरी सरणी को सॉर्ट कर सकते हैं।

हीप सॉर्ट तकनीक की जटिलता

• समय की जटिलता: ओ (एन लॉग एन)
• अंतरिक्ष जटिलता: ओ(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

हीपसॉर्ट (सरणी, आकार)

इनपुट: डेटा की एक सरणी, और सरणी में कुल संख्या

आउटपुट −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