Step by step animation. For the programming beginners to get a better understanding of heap and heap sort.
In the animation, the heap in tree structure just let you know how it works. The entire coding is using array rather than binary tree. (Click snail button to start animation and click it again to go back to the first page)
For an element with index i in the array
Its parent index is: (i-1)/2
Its left child index is: 2*i+1
Its right child index is: 2*i+2
Cost: O(nlogn)
Worst case: O(nlogn)
Best case: O(nlogn)
Heap sort code in C++:
In the animation, the heap in tree structure just let you know how it works. The entire coding is using array rather than binary tree. (Click snail button to start animation and click it again to go back to the first page)
For an element with index i in the array
Its parent index is: (i-1)/2
Its left child index is: 2*i+1
Its right child index is: 2*i+2
Cost: O(nlogn)
Worst case: O(nlogn)
Best case: O(nlogn)
Heap sort code in C++:
void
swap(int i, int
j,int a[])
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
void
heapify(int i,int
a[],int heapSize)
{
int temp=i;
while(i*2+1<=heapSize-1)
{
if(i*2+2<=heapSize-1&&a[i*2+2]>a[i*2+1])
{
i=i*2+2;
}
else i=i*2+1;
if(a[i]>a[temp])
{
swap(i,temp,a);
temp=i;
}
else break;
}
}
void BuildMaxHeap(int
a[],int heapSize)
{
int i=(heapSize-1)/2;
while(i>=0)
{
heapify(i,a,heapSize);
i--;
}
}
void
heapSort(int a[],int
heapSize)
{
for(int
i=heapSize;i>0;i--)
{
swap(0,heapSize-1,a);
heapSize--;
heapify(0,a,heapSize);
}
}
int
main()
{
int
heapSize=7;
int
a[]={25,49,8,25,21,16,32};
BuildMaxHeap(a,heapSize);
heapSort(a,heapSize);
Thank you so much! You've been so helpful. Though there are some typos in the animation .. I did some minor changes to your code in Java for other beginners to try out themselves =)
ReplyDeleteHi Victor, Thanks for your code! I fixed the typo I saw "frist". I am glad this post can be helpful.
Deleteimport java.util.Arrays;
ReplyDeletepublic class heapSort {
static void swap(int i, int j, int [] a) {
int temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
static void heapify(int j, int heapSize, int [] a){
int temp = j;
while (j*2 + 1 <= heapSize -1){
if(j*2+2 <= heapSize -1 && a[j*2+2] > a[j*2+1]){
j = j*2 +2;
}else{
j = j*2 +1;
}
if(a[j] > a[temp]){
swap(j,temp,a);
temp = j;
}else{
break;
}
}
}
static void BuildMaxHeap(int [] a, int heapSize){
int i = (heapSize -1)/2;
while (i >= 0 ){
heapify(i,heapSize,a);
i--;
}
}
static void heapSort(int [] a, int heapSize){
for (int i = heapSize; i>0;i--){
swap(0,heapSize-1,a);
heapSize--;
heapify(0,heapSize,a);
}
}
public static void main (String [] args){
//i and j = (heapSize -1)/2
int [] a = {25,49,8,25,21,16,32};
int heapSort = 7;
BuildMaxHeap(a,heapSort);
heapSort(a,heapSort);
System.out.println(Arrays.toString(a));
}
}