e , based on 1, you will find a rule. To a node n, it must have the fellowing relationship:
* parent : floor(n/2)
* left chil : 2*n
* right chil : 2*n + 1
*
* This feature gives us a chance to save a tree into a array.
*
* 2). What is max heapify ?
* --For a binary tree, if all of parent nodes greater than or equal to those corresponding child nodes, the root node must be the largest node in this tree. In other words,
* we can get the largest one between some nodes by arrange those number into a max binary tree. By the way, if binary tree can do that, then heap can, too.
*/
/*
* The Heapsort algorithm can be divided into two parts.
* step 1: build a max binary tree.
*
* step 2: remove the largest node( the root of the tree) ,and then update the tree repeatedly untill all of nodes has been get out.
*
*/
5.1 core code
bool HeapSort::sort(void)
{
/*
* As we all know, some of nodes haven't child node.
* For skip those nodes, we need to find the last parent node.
*
* but How can we do that?
*
* --the answer is the last child node.
*/
INDEX nInd = 0;
nInd = this->fun.GetParentInd( this->right );
/*
* Adjust nodes from bottom to top.Function MaxHeapify()
* will arrange a node and its's sublayer nodes to
* a max binary tree.
*/
while( nInd>=0)
{
// @(this->right) is the number of nodes.
this->MaxHeapify( nInd, this->right);
nInd--;
}
/*
* moving the largest one between all of nodes into a array,
* and tidy the remaining. Repeat this process untill
* we get all of nodes.
*/
nInd = this->right;
while( nInd>0 )
{
this->Swap( 0, nInd);
nInd --;
this->MaxHeapify( 0, nInd);
}
return true;
}
bool HeapSort::MaxHeapify( INDEX nInd, INDEX right)
{
INDEX max = this->GetBigNodeInd( nInd, right);
while( max!=nInd)
{
this->Swap( max, nInd);
nInd = max;
max = this->GetBigNodeInd( nInd, right);
}
return true;
}
/*
* About @MaxHeapify(), there are many problems need to solve. This article is worth to reading:
* http://shmilyaw-hotmail-com.iteye.com/blog/1775868
*
*/
5.2 Time complexity
/**
* sorry, I have no idea.
*/
5.3 Space complexity
/**
* space complexity
*
* It is simple to compute the space complexity.
* S(n) = O(1);
* because it use a constant space.
*/
/*
* The totally example source code is here:
*
* (It maybe some fault, I will glad to your advices)
*/
/**
* References:
*
* heap sort分析和总结
* heapsort
*
*/