Descending heap sort using min-heap-C++-php.cn

Descending heap sort using min-heap

Heap Sort- Heap sort is a comparison-based algorithm that uses a binary tree data structure to sort a list of numbers in ascending or descending order. It creates a heap data structure by heap sorting where the root is the smallest element, then removes the root and sorts again giving the second smallest number in the list at the root position.

Min Heap- A min heap is a data structure in which the parent node is always smaller than the child node, so the root node is the smallest element among all elements.

Problem Statement

Given an array of integers. Sort them in descending order using min-heap.

Example 1

Input: [2, 5, 1, 7, 0]

Copy after login

Output: [7, 5, 2, 1, 0]

Copy after login

Example 2

Input: [55, 1, 23, 10, 1]

Copy after login

Output: [55, 23, 10, 1, 1]

Copy after login

method 1

To perform a heap sort in descending order using a min-heap, we create a min-heap of elements and extract one element at a time to get an array in descending order by reversing the order.

pseudocode

procedure heapSort (arr[], n) Initialize priority queue: minHeap for i = 1 to n add arr[i] to minHeap i = n - 1 while minHeap is not empty arr[i–] = top element of minHeap Remove the top element of minHeap end procedure

Copy after login

Example: C implementation

In the following program, we sort the array using min-heap and then reverse the order to get the result.

#include  using namespace std; // Function to heap sort in decreasing order using min heap void heapSort(int arr[], int n){ // Creating min heap using a priority queue priority_queue, greater > minHeap; // Inserting input array to min heap for (int i = 0; i < n; i++){ minHeap.push(arr[i]); } // Iterating backwards in the input array, where each element is replaced by the smallest element extracted from min heap int i = n - 1; while (!minHeap.empty()){ arr[i--] = minHeap.top(); minHeap.pop(); } } int main(){ int arr[6] = {5, 2, 9, 1, 5, 6}; int n = 6; heapSort(arr, n); cout << "Sorted array : "; for (int i = 0; i < n; i++){ cout << arr[i] << " "; } cout << endl; return 0; }

Copy after login

Output

Sorted array : 9 6 5 5 2 1

Copy after login

Time complexity- O(nlogn)

Space complexity- O(n)

Method 2

Another solution to this problem is to build a min-heap starting from the last non-leaf root pattern and working backwards. We can then sort the array by swapping the root node and the last leaf node, and then restore the min-heap property.

pseudocode

procedure heapify (arr[], n , i) smallest = i l = 2i + 1 r = 2i + 2 if l < n and arr[l] < arr[smallest] smallest = l end if if r < n and arr[r] < arr[samllest] smallest = r end if if smallest is not i swap arr[i] to arr[smallest] heapify (arr, n, smallest) end if end procedure procedure heapSort (arr[], n) for i = n/2 - 1 to 0 heapify(arr, n, i) for i = n-1 to 0 swap arr[0] to arr[i] heapify (arr, i, 0) end procedure

Copy after login

Example: C implementation

In the following program, we use the heapify() function to restore the min-heap properties of the subtree rooted at index i, and use heapSort() to build the min-heap in reverse order.

#include  using namespace std; // Restores the min heap property of subtree rooted at index i void heapify(int arr[], int n, int i){ int smallest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] < arr[smallest]){ smallest = l; } if (r < n && arr[r] < arr[smallest]){ smallest = r; } if (smallest != i){ swap(arr[i], arr[smallest]); heapify(arr, n, smallest); } } void heapSort(int arr[], int n){ // Build the min heap in reverse order for (int i = n / 2 - 1; i >= 0; i--){ heapify(arr, n, i); } // Sort the array by repeatedly swapping the root node with the last leaf node for (int i = n - 1; i >= 0; i--){ swap(arr[0], arr[i]); heapify(arr, i, 0); } } int main(){ int arr[6] = {5, 2, 9, 1, 5, 6}; int n = 6; heapSort(arr, n); cout << "Sorted array : "; for (int i = 0; i < n; i++){ cout << arr[i] << " "; } cout << endl; return 0; }

Copy after login

Output

Sorted array : 9 6 5 5 2 1

Copy after login

Using the previous method of creating a min-heap using the heapSort() function, we can use the same method in this solution, but instead of using heapify to restore the properties of the min-heap, we use the traditional hep sorting algorithm to create amin The order of heap and sorted elements is incremented and further reversed to obtain the desired output.

pseudocode

procedure heapSort (arr[], n) for i = n/2 - 1 to 0 parent = i while parent *2+1 < n child = parent*2+1 if child+1 < n and arr[child] >arr[child+1] child = child + 1 end if if arr[parent] > arr[child] swap arr[parent] to arr[child] parent = child else break end if for i = n-1 to 0 swap arr[0] to arr[i] parent = 0 while parent*2+1 < i child = parent*2+1 if child+1 < n and arr[child] >arr[child+1] child = child + 1 end if if arr[parent] > arr[child] swap arr[parent] to arr[child] parent = child else break end if end procedure

Copy after login

Example: C implementation

In the following program, we modify the heap sort algorithm to sort the array in descending order.

#include  using namespace std; void heapSort(int arr[], int n){ // Building min heap in reverse order for (int i = n / 2 - 1; i >= 0; i--) { // Starting from last parent node, apply heapify operation int parent = i; while (parent * 2 + 1 < n) { int child = parent * 2 + 1; if (child + 1 < n && arr[child] > arr[child + 1]){ child++; } if (arr[parent] > arr[child]){ swap(arr[parent], arr[child]); parent = child; } else{ break; } } } // Extarct elekemnhts form min heap in decreasing order for (int i = n - 1; i > 0; i--){ swap(arr[0], arr[i]); int parent = 0; // Perform heapify operation at new root node while (parent * 2 + 1 < i){ int child = parent * 2 + 1; if (child + 1 < i && arr[child] > arr[child + 1]){ child++; } if (arr[parent] > arr[child]){ swap(arr[parent], arr[child]); parent = child; } else { break; } } } } int main(){ int arr[6] = {5, 2, 9, 1, 5, 6}; int n = 6; heapSort(arr, n); cout << "Sorted array : "; for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; return 0; }

Copy after login

Output

Sorted array : 9 6 5 5 2 1

Copy after login

in conclusion

In summary, in order to perform a descending heap sort using a min-heap, we can use a variety of methods, some of which have a time complexity of O(nlogn), and each method has a different space complexity.

The above is the detailed content of Descending heap sort using min-heap. For more information, please follow other related articles on the PHP Chinese website!