For heap sort, we need to interpret the given input array as a binary tree. We are going to follow deleteMax routine to perform heap sort. We need to follow the below heap property to build binary heap.
Heap order property:
Key in parent node needs to greater than the key in its children nodes.
---------------------------------------
Input: | 60 | 50 | 65 | 42 | 10 | 34 | 23 |
---------------------------------------
0 1 2 3 4 5 6
Interpretation of given input array as binary heap:
Here 'i' is the index of the array. For any element in the given input array, the position of its left child is 2i + 1 and the position of right child is (2i + 1 + 1).
left child of 60(index 'i' is 0) = 2(0) + 1 => 50 is present at the index '1'.
right child of 60(index '1' is 0) = 2(0) + 2 => 65 is present at the index '2'.
i = 0; input[0] = 60
left node of input[0] = input[ 2 * 0 + 1] => input[1] = 50
right node of input[0] = input[ 2 * 0 + 2] => input[2] = 65
Similarly, we can find left and right children of any node in the given input array and build the binary heap.
60
/ \
50 65
/ \ / \
42 10 34 23
Apply heap order property to the above binary tree.
60
/ \
50 65
/ \ / \
42 10 34 23
65 > 35(leftchild) and 23(rightchild).
50 > 42(leftchild) and 10(rightchild).
60 > 50(leftchild). But, it is not greater than the key value in its right child(65). So, swap 60 and 65.
65
/ \
50 60
/ \ / \
42 10 34 23
So, the above heap satisfies heap order property. Instead of using additional array to save the sorted elements, we use same array to store sorted elements. This saves significant amount of space and time for us.
Apply deletMax routine to the heap.
Swap first and last element in our binary heap and delete the max element(65) from the heap.
23
/ \
50 60
/ \ / \
42 10 34 65
23
/ \
50 60
/ \ /
42 10 34
----------------------------------------
Input: | 23 | 50 | 60 | 42 | 10 | 34 | 65 |
----------------------------------------
Here, we are reusing the given input array to store sorted data. At this stage, the last element in the input array is sorted and the size of the heap shrinks by 1(after every deletemax operation).
Below heap is not satisfying heap order property.
23
/ \
50 60
/ \ /
42 10 34
50 > 42 and 10
60 > 34
23 is less than its left and right child. Reconstruct heap until it satisfies heap order property.
60
/ \
50 23
/ \ /
42 10 34
60
/ \
50 34
/ \ /
42 10 23
Above heap satisfies heap order property.
---------------------------------------
Input: | 60 | 50 | 34 | 42 | 10 | 23 | 65 |
----------------------------------------
Apply deleteMax routine to the above heap.
23
/ \
50 34
/ \ /
42 10 60
23
/ \
50 34
/ \
42 10
-----------------------------------------
Input: | 23 | 50 | 34 | 42 | 10 | 60 | 65 |
-----------------------------------------
Reconstruct heap until it satisfies heap order property.
50
/ \
23 34
/ \
42 10
50
/ \
42 34
/ \
23 10
Apply deleteMax routine to the above heap.
10
/ \
42 34
/ \
23 50
10
/ \
42 34
/
23
-----------------------------------------
Input: | 10 | 42 | 34 | 23 | 50 | 60 | 65 |
-----------------------------------------
Reconstruct heap until it satisfies heap order property.
42
/ \
10 34
/
23
42
/ \
23 34
/
10
Apply deleteMax routine to the above heap.
10
/ \
23 34
/
42
10
/ \
23 34
------------------------------------------
Input: | 10 | 23 | 34 | 42 | 50 | 60 | 65 |
------------------------------------------
Re-construct heap until it satisfies heap order property.
34
/ \
23 10
Apply deleteMax routine to the above heap. Swap first and last element of the heap. Then, delete the max element from the heap.
10
/ \
23 34
10
/
23
------------------------------------------
Input: | 10 | 23 | 34 | 42 | 50 | 60 | 65 |
------------------------------------------
Reconstruct the above heap.
23
/
10
Apply deleteMax Routine.
10
/
23
10
-------------------------------------------
Input: | 10 | 23 | 34 | 42 | 50 | 60 | 65 |
-------------------------------------------
Add 10 to the ouput array and the resultant elements in the input array would be in sorted order.
See Also:
C Program To Perform Insertion Sort
C Program To Perform Shell Sort
C Program To Perform Bubble Sort
C Program To Perform Quick Sort
C Program To Perform Radix Sort
C Program To Perform Selection Sort
C Program To Perform Heap Sort
C Program To Perform Merge Sort
C Program To Perform External Sorting
C Program To Perform Sorting Using Binary Search Tree
Example Program To Implement Heap Sort:
Heap order property:
Key in parent node needs to greater than the key in its children nodes.
---------------------------------------
Input: | 60 | 50 | 65 | 42 | 10 | 34 | 23 |
---------------------------------------
0 1 2 3 4 5 6
Interpretation of given input array as binary heap:
Here 'i' is the index of the array. For any element in the given input array, the position of its left child is 2i + 1 and the position of right child is (2i + 1 + 1).
left child of 60(index 'i' is 0) = 2(0) + 1 => 50 is present at the index '1'.
right child of 60(index '1' is 0) = 2(0) + 2 => 65 is present at the index '2'.
i = 0; input[0] = 60
left node of input[0] = input[ 2 * 0 + 1] => input[1] = 50
right node of input[0] = input[ 2 * 0 + 2] => input[2] = 65
Similarly, we can find left and right children of any node in the given input array and build the binary heap.
60
/ \
50 65
/ \ / \
42 10 34 23
Apply heap order property to the above binary tree.
60
/ \
50 65
/ \ / \
42 10 34 23
65 > 35(leftchild) and 23(rightchild).
50 > 42(leftchild) and 10(rightchild).
60 > 50(leftchild). But, it is not greater than the key value in its right child(65). So, swap 60 and 65.
65
/ \
50 60
/ \ / \
42 10 34 23
So, the above heap satisfies heap order property. Instead of using additional array to save the sorted elements, we use same array to store sorted elements. This saves significant amount of space and time for us.
Apply deletMax routine to the heap.
Swap first and last element in our binary heap and delete the max element(65) from the heap.
23
/ \
50 60
/ \ / \
42 10 34 65
23
/ \
50 60
/ \ /
42 10 34
----------------------------------------
Input: | 23 | 50 | 60 | 42 | 10 | 34 | 65 |
----------------------------------------
Here, we are reusing the given input array to store sorted data. At this stage, the last element in the input array is sorted and the size of the heap shrinks by 1(after every deletemax operation).
Below heap is not satisfying heap order property.
23
/ \
50 60
/ \ /
42 10 34
50 > 42 and 10
60 > 34
23 is less than its left and right child. Reconstruct heap until it satisfies heap order property.
60
/ \
50 23
/ \ /
42 10 34
60
/ \
50 34
/ \ /
42 10 23
Above heap satisfies heap order property.
---------------------------------------
Input: | 60 | 50 | 34 | 42 | 10 | 23 | 65 |
----------------------------------------
Apply deleteMax routine to the above heap.
23
/ \
50 34
/ \ /
42 10 60
23
/ \
50 34
/ \
42 10
-----------------------------------------
Input: | 23 | 50 | 34 | 42 | 10 | 60 | 65 |
-----------------------------------------
Reconstruct heap until it satisfies heap order property.
50
/ \
23 34
/ \
42 10
50
/ \
42 34
/ \
23 10
Apply deleteMax routine to the above heap.
10
/ \
42 34
/ \
23 50
10
/ \
42 34
/
23
-----------------------------------------
Input: | 10 | 42 | 34 | 23 | 50 | 60 | 65 |
-----------------------------------------
Reconstruct heap until it satisfies heap order property.
42
/ \
10 34
/
23
42
/ \
23 34
/
10
Apply deleteMax routine to the above heap.
10
/ \
23 34
/
42
10
/ \
23 34
------------------------------------------
Input: | 10 | 23 | 34 | 42 | 50 | 60 | 65 |
------------------------------------------
Re-construct heap until it satisfies heap order property.
34
/ \
23 10
Apply deleteMax routine to the above heap. Swap first and last element of the heap. Then, delete the max element from the heap.
10
/ \
23 34
10
/
23
------------------------------------------
Input: | 10 | 23 | 34 | 42 | 50 | 60 | 65 |
------------------------------------------
Reconstruct the above heap.
23
/
10
Apply deleteMax Routine.
10
/
23
10
-------------------------------------------
Input: | 10 | 23 | 34 | 42 | 50 | 60 | 65 |
-------------------------------------------
Add 10 to the ouput array and the resultant elements in the input array would be in sorted order.
See Also:
C Program To Perform Insertion Sort
C Program To Perform Shell Sort
C Program To Perform Bubble Sort
C Program To Perform Quick Sort
C Program To Perform Radix Sort
C Program To Perform Selection Sort
C Program To Perform Heap Sort
C Program To Perform Merge Sort
C Program To Perform External Sorting
C Program To Perform Sorting Using Binary Search Tree
Example Program To Implement Heap Sort:
#include <stdlib.h>
#define lchild(j) ((2 * j) + 1)
void processHeap(int *data, int i, int n) {
int mchild, temp, j;
for (temp = data[i]; lchild(i) < n; i = mchild) {
mchild = lchild(i);
/*
* value in parent node needs to greater than
* its children.
*/
if (mchild != n-1 && data[mchild] < data[mchild+1])
mchild++;
if (temp < data[mchild])
data[i] = data[mchild];
else
break;
}
data[i] = temp;
}
/* heap sort using delete maximum property */
void heapSort(int *data, int n) {
int i, temp, j;
/*
* Build Binary Heap property - the value
* in parent node should be greater than
* its children.
*/
for (i = n/2; i >= 0; i--) {
processHeap(data, i, n);
}
/*
* Sort elements in heap using delete max property.
* After building heap, we have max element at the
* root node. So, we need to swap the root and the
* the last element in the heap(array) and re-apply
* build binary heap property to the elements present
* previous to current last element.
*/
for (i = n-1; i > 0; i--) {
temp = data[0];
data[0] = data[i];
data[i] = temp;
processHeap(data, 0, i);
}
}
int main() {
int n, i, *data;
printf("Enter your no of entries:");
scanf("%d", &n);
data = (int *)malloc(sizeof (int) * n);
/* input data from the user */
for (i = 0; i < n; i++)
scanf("%d", &data[i]);
heapSort(data, n);
printf("Data after sorting:\n");
for (i = 0; i < n; i++)
printf("%3d ", data[i]);
printf("\n");
return 0;
}
Output: (C Program To Implement Heap Sort)
jp@jp-VirtualBox:$ ./a.out
Enter your no of entries:7
60 50 65 42 10 34 23
Data after sorting:
10 23 34 42 50 60 65
Enter your no of entries:7
60 50 65 42 10 34 23
Data after sorting:
10 23 34 42 50 60 65
Sir I have some problem to understand this problem. When I try to understand this code with dry run that time I didn't understand anything. What is mchild here
ReplyDelete