HeapSort(堆排序 C++)(二)
int maxIndex = i; // In a 3 elements heap, we assume the node is the max element.
if(left > a[i]){ // If node's left child value is big than node
maxIndex = leftIndex; // we change the maxIndex value to left child's index
}
if(leftIndex + 1 < n && a[leftIndex + 1] > a[maxIndex]){ //if we have the right child, and right child's value is big
// than the max value of the two(node and its left child)
maxIndex = leftIndex + 1; // we change the maxIndex value to right child's index
}
if(maxIndex != i){ // if some child of the node is big than the node's value
swap(a[i], a[maxIndex]); // we exchange the two elements
}else{
break;
}
//---------------find the max element in the three element, and exchange the two elements. end ----------------------
i = maxIndex; // Because we exchange some value,so we will look down from the element we had changed,
// So we change the node index to the max value's index,change the left index
leftIndex = 2 * i + 1;
}
}*/
//The best one.
template
//adjust elements from i to n.
void MaxHeapify(T a[], int i, int n)
{
int leftIndex, node;
node = a[i];
leftIndex = 2 * i + 1;
while (leftIndex < n)
{
//---------- finding a max element in left child and right child--------------
if (leftIndex + 1 < n && a[leftIndex + 1] >
a[leftIndex])
leftIndex++;
//---------- finding a max element in left child and right child--------------
if (a[leftIndex] <= node)
break;
a[i] = a[leftIndex];
i = leftIndex;
leftIndex = 2 * i + 1;
}
a[i] = node;
}
template
void BuildMaxHeap(T a[], int n){
for(int i = n/2 - 1; i >= 0; i--){
MaxHeapify(a, i ,n);
}
}
template
void HeapSort(T a[], int n){
for(int i = n - 1; i >= 1;i--){
swap(a[0],a[i]);
MaxHeapify(a, 0, i); // rebuild max heap
}
}
template
void PrintfNum(T a[], int n);
int main(int argc, char* argv[])
{
const int NUM = 10;
int a[NUM]={4,1,3,2,16,9,10,14,8,7};
cout << "Before sort:" << endl;
int flag;
PrintfNum(a, NUM);
cout << "Build Max Heap:" << endl;
BuildMaxHeap(a, NUM);// building a max heap
PrintfNum(a, NUM);
cout << "After Heap Sort:" << endl;
HeapSort(a, NUM);
PrintfNum(a, NUM);
return 0;
}
template
void PrintfNum(T a[], int n){
for(int i = 0; i < n; i++){
cout << a[i] << ",";
}
cout << endl;
}
