In heap sorting process:
First of all organizing the whole data to be sorted as a binary tree i.e. heap. And after that impletment heap sorting.
Step 1: (How to data organizing as binary tree?)
Remember only 2 rule:
Rule:1.
The parent node must be greater then child node.
If parent node is not greater then to child node not replace it with parent node. And if binary tree is large then, if relaceing child node(now its parent node) is greater then to great-parent node then its also is replace the great-parent node.
Rule:2.
New element always insert in left side and after right side of parent node.
If left side of parent element has already element then new element would be insert in right side. And if right side of parent node has already element then new element will be insert in left side.
Step 2: (How to perform heap sorting:)
Remove the topmost element(largest element) and replace it with the rightmost element.
Heap Sorting method/process by example:
max heap : 80 , 32 , 31 , 110 , 50 , 40 , 120
Step1:
80
Step2:
80
/ \
32 31
Step3:
80 80 110
/ \ / \ / \
32 31 ==> 110 31 ==> 80 31
/ / /
110 32 32
Step4:
110
/ \
80 31
/ \
32 5
Step5:
110 110
/ \ / \
80 31 ==> 80 40
/ \ / / \ /
32 50 40 32 50 31
Step6:
110 110 120
/ \ / \ / \
80 40 ==> 80 120 ==> 80 110
/ \ / \ / \ / \ / \ / \
32 50 31 120 32 50 31 40 32 50 31 40
-------------------------------------------------------------------------------------
(1)
120 [1]
/ \
80 [2] 110 [3]
/ \ / \
32 [4] 50 [5] 31 [6] 40 [7]
// [1],[2],[3],[4],[5],[6],[7]: Index number
// Now applying step 2(perform heap sorting)
// Replace the topmost element with the rightmost element.
(2)
40 110
/ \ Heaping / \
80 110 =====> 80 40
/ \ / \ / \ / \
32 50 31 120 32 50 31 120
(3)
//now replace 110 with rightmost element i.e. 31 because 120 had been sorted.
31 80 80
/ \ Heaping / \ Heaping / \
80 40 ======> 31 40 ======> 50 40
/ \ / \ / \ / \ / \ / \
32 50 110 120 32 50 110 120 32 31 110 120
(4)
//now replace 80 with rightmost element i.e. 31 because 110, 120 had been sorted.
31 50 50
/ \ Heaping / \ Heaping / \
50 40 ======> 31 40 ======> 32 40
/ \ / \ / \ / \ / \ / \
32 80 110 120 32 80 110 120 31 80 110 120
(5)
//now replace 50 with rightmost element i.e. 31 because 80, 110, 120 had been sorted.
31 40
/ \ Heaping / \
32 40 ======> 32 31
/ \ / \ / \ / \
50 80 110 120 50 80 110 120
(6)
//now replace 40 with rightmost element i.e. 31 because 50, 80, 110, 120 had been sorted.
31 32
/ \ Heaping / \
32 40 ======> 31 40
/ \ / \ / \ / \
50 80 110 120 50 80 110 120
(7)
//now replace 32 with rightmost element i.e. 31 because 40, 50, 80, 110, 120 had been sorted.
31
/ \
32 40
/ \ / \
50 80 110 120
Now all elements are sorted: 31 , 32 , 40 , 50 , 80 , 110 , 120
First of all organizing the whole data to be sorted as a binary tree i.e. heap. And after that impletment heap sorting.
Step 1: (How to data organizing as binary tree?)
Remember only 2 rule:
Rule:1.
The parent node must be greater then child node.
If parent node is not greater then to child node not replace it with parent node. And if binary tree is large then, if relaceing child node(now its parent node) is greater then to great-parent node then its also is replace the great-parent node.
Rule:2.
New element always insert in left side and after right side of parent node.
If left side of parent element has already element then new element would be insert in right side. And if right side of parent node has already element then new element will be insert in left side.
Step 2: (How to perform heap sorting:)
Remove the topmost element(largest element) and replace it with the rightmost element.
Step 3:
Repeat steps 1 and 2 untill all elements is not sorted.
Heap Sorting method/process by example:
max heap : 80 , 32 , 31 , 110 , 50 , 40 , 120
Step1:
80
Step2:
80
/ \
32 31
Step3:
80 80 110
/ \ / \ / \
32 31 ==> 110 31 ==> 80 31
/ / /
110 32 32
Step4:
110
/ \
80 31
/ \
32 5
Step5:
110 110
/ \ / \
80 31 ==> 80 40
/ \ / / \ /
32 50 40 32 50 31
Step6:
110 110 120
/ \ / \ / \
80 40 ==> 80 120 ==> 80 110
/ \ / \ / \ / \ / \ / \
32 50 31 120 32 50 31 40 32 50 31 40
-------------------------------------------------------------------------------------
(1)
120 [1]
/ \
80 [2] 110 [3]
/ \ / \
32 [4] 50 [5] 31 [6] 40 [7]
// [1],[2],[3],[4],[5],[6],[7]: Index number
// Now applying step 2(perform heap sorting)
// Replace the topmost element with the rightmost element.
(2)
40 110
/ \ Heaping / \
80 110 =====> 80 40
/ \ / \ / \ / \
32 50 31 120 32 50 31 120
(3)
//now replace 110 with rightmost element i.e. 31 because 120 had been sorted.
31 80 80
/ \ Heaping / \ Heaping / \
80 40 ======> 31 40 ======> 50 40
/ \ / \ / \ / \ / \ / \
32 50 110 120 32 50 110 120 32 31 110 120
(4)
//now replace 80 with rightmost element i.e. 31 because 110, 120 had been sorted.
31 50 50
/ \ Heaping / \ Heaping / \
50 40 ======> 31 40 ======> 32 40
/ \ / \ / \ / \ / \ / \
32 80 110 120 32 80 110 120 31 80 110 120
(5)
//now replace 50 with rightmost element i.e. 31 because 80, 110, 120 had been sorted.
31 40
/ \ Heaping / \
32 40 ======> 32 31
/ \ / \ / \ / \
50 80 110 120 50 80 110 120
(6)
//now replace 40 with rightmost element i.e. 31 because 50, 80, 110, 120 had been sorted.
31 32
/ \ Heaping / \
32 40 ======> 31 40
/ \ / \ / \ / \
50 80 110 120 50 80 110 120
(7)
//now replace 32 with rightmost element i.e. 31 because 40, 50, 80, 110, 120 had been sorted.
31
/ \
32 40
/ \ / \
50 80 110 120
Now all elements are sorted: 31 , 32 , 40 , 50 , 80 , 110 , 120
Related programs:
- Merge sorting
- Heap sorting
- Bubble sorting
- Selection Sorting
- Insertion sorting
- Insertion sorting using function
- Shell sorting
- Quick sorting
- Radix sorting
- Liner sorting
the way heap sort is explained through example is really appreciable.
ReplyDeletevery nice explaination.. i was struggling through various links.. no one has explained it as neatly as here
ReplyDeletegreat post!
ReplyDeletevery well explained
ReplyDeletereally nice explaination
ReplyDeletereally nice explaination
ReplyDeletePerfect !!
ReplyDelete