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);
