Sorting Algorithms: Analysis of Heapsort

no_mkd

1. Pros and Cons of Heapsort

(Briefly discussing this, as there's no need to waste time understanding a poor algorithm.)

Pros:

The efficiency of heapsort is comparable to quicksort and mergesort, reaching the peak efficiency for comparison-based sorting algorithms (time complexity of O(n log n)).
Beyond efficiency, the biggest highlight is that it only requires O(1) auxiliary space. It is uniquely both highly efficient and extremely space-saving.
Heapsort's efficiency is relatively stable, unlike quicksort which can degrade to O(n^2) in the worst case. Therefore, whether the input sequence is ordered or not, heapsort consistently maintains a complexity of O(n log n) (note that "stable" here refers to average time complexity equaling worst-case complexity, not "stability" in the sorting sense, as heapsort itself is unstable).

Cons: (Given the above, heapsort seems nearly perfect. So why is quicksort, rather than heapsort, the most commonly used internal sorting algorithm?)

The biggest and only disadvantage is the maintenance of the heap. In real-world scenarios, data changes frequently. For every update (addition, deletion, or modification) to the sequence, the heap must be maintained again to preserve its properties, which is unnecessary in most cases. (This is why quicksort is the king of practical applications, while heapsort often remains an academic favorite... though that might be slightly unfair; when data updates are infrequent, heapsort is indeed superior...)

2. Internal Principles

First, understand the steps of heapsort:

Build the initial heap, constructing the first max-heap or min-heap from the input sequence. (What are max-heaps and min-heaps? No need to explain; think of a haystack...)
Swap the root with the last element, "cut the tail," and rebuild the heap from the remaining elements.
Repeat the second step until only the root remains; sorting is then complete.

Sorting with a min-heap results in descending order (or non-ascending, don't sweat the details...), while sorting with a max-heap results in ascending order.

The statement above might seem incorrect at first glance (in a min-heap, the smallest element is at the top, a[0]; how can that lead to descending order?). Do not doubt its correctness; the following diagrams will make it clear:

Assume the input sequence is a[] = {7, 1, 6, 5, 3, 2, 4}, and we are sorting in ascending order using a max-heap.

Step 1 (Build Initial Heap):

{7, 5, 6, 1, 3, 2, 4} now satisfies the max-heap property. Step one is complete.

Step 2 (Swap Root and Tail, Cut the Tail, Rebuild):

Step 3 (Repeat Step 2 until all tails are cut):

No image here; drawing in MS Paint is too exhausting. Step 2 should be enough; the rest can be easily drawn by hand.

The core concept is "cutting the tail." Unfortunately, most resources don't explicitly state this, yet is there any description more fitting than "cutting the tail"?

3. Implementation Details

The diagrams in the principle introduction essentially explain the implementation details, so we will focus purely on the code here.

First, my own implementation using a max-heap:

#include<stdio.h>
//构造大根堆（让a[m]到a[n]满足大根堆）
void HeapAdjust(int a[], int m, int n){
int temp;
int max;
int lc;//左孩子
int rc;//右孩子
while(1){
	//获取a[m]的左右孩子
	lc = 2 * m + 1;
	rc = 2 * m + 2;
	//比较a[m]的左右孩子，max记录较大者的下标
	if(lc &gt;= n){
		break;//不存在左孩子则跳出
	}
	if(rc &gt;= n){
		max = lc;//不存在右孩子则最大孩子为左孩子
	}
	else{
		max = a[lc] &gt; a[rc] ? lc : rc;//左右孩子都存在则找出最大孩子的下标
	}
	//判断并调整（交换）
	if(a[m] &gt;= a[max]){//父亲比左右孩子都大，不需要调整，直接跳出
		break;
	}
	else{//否则把小父亲往下换
		temp = a[m];
		a[m] = a[max];
		a[max] = temp;
		//准备下一次循环，注意力移动到孩子身上，因为交换之后以孩子为根的子树可能不满足大根堆
		m = max;
	}
}

}
void HeapSort(int a[], int n){
int i,j;
int temp;
//自下而上构造小根堆（初始堆）
for(i = n / 2 - 1;i &gt;= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点（叶子节点已经满足小根堆，只需要调整所有的非叶子节点），一点小小的优化
	HeapAdjust(a, i, n);
}

printf("初始堆: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

for(i = n - 1;i &gt; 0;i--){
	//首尾交换，断掉尾巴
	temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	//断尾后的部分重新调整
	HeapAdjust(a, 0, i);

	/*
	printf("第%d次（i - 1 = %d）: ", n - i, i - 1);
	for(j = 0;j &lt; n;j++){
		printf("%d ", a[j]);
	}
	printf("\n");
	*/
}

}
main(){
//int a[] = {5, 6, 3, 4, 1, 2, 7};
//int a[] = {1, 2, 3, 4, 5, 6, 7};
//int a[] = {7, 6, 5, 4, 3, 2, 1};
int a[] = {7, 1, 6, 5, 3, 2, 4};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("结果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S. The comments are extremely detailed because I wrote this following my own logical progression. It should be easy to understand by reading the code.

Next is the textbook implementation using a max-heap:

#include<stdio.h>
void HeapAdjust(int a[], int m, int n){
int i;
int t = a[m];
for(i = 2 * m + 1;i &lt;= n;i = 2 * i + 1){
	if(i &lt; n &amp;&amp; a[i + 1] &gt; a[i])++i;
	if(t &gt;= a[i])break;
	//把空缺位置往下放
	a[m] = a[i];
	m = i;
}
a[m] = t;//只做一次交换，步骤上的优化

}
void HeapSort(int a[], int n){
int i;
int t;
//自下而上构造大根堆
for(i = n / 2 - 1;i &gt;= 0;--i){
	HeapAdjust(a, i, n - 1);
}

printf("初始堆: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

for(i = n - 1;i &gt; 0;i--){
	//首尾交换，断掉尾巴
	t = a[i];
	a[i] = a[0];
	a[0] = t;
	//对断尾后的部分重新建堆
	HeapAdjust(a, 0, i - 1);
}

}
main(){
//int a[] = {5, 6, 3, 4, 1, 2, 7};
//int a[] = {1, 2, 3, 4, 5, 6, 7};
//int a[] = {7, 6, 5, 4, 3, 2, 1};
int a[] = {7, 1, 6, 5, 3, 2, 4};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("结果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S. The textbook code is much shorter, featuring both architectural and procedural optimizations. The subtle differences are noted in the comments. However, this level of optimization significantly reduces readability, which is why textbook algorithms are often daunting. (In practice, we can optimize textbook code for form, maintaining efficiency while improving readability...)

Finally, here is an implementation using a min-heap, written after studying the textbook optimizations (most online resources use max-heaps; this is just to keep things fresh...):

#include<stdio.h>
//构造小根堆（让a[m]到a[n]满足小根堆）
void HeapAdjust(int a[], int m, int n){
int i;
int t = a[m];
int temp;
for(i = 2 * m + 1;i &lt;= n;i = 2 * i + 1){
	//a[m]的左右孩子比较，i记录较小者的下标
	if(i &lt; n &amp;&amp; a[i + 1] &lt; a[i]){
		i = i + 1;
	}
	if(t &lt;= a[i]){
		break;
	}
	else{//把空缺位置往下换
		//把较小者换上去
		temp = a[m];
		a[m] = a[i];
		a[i] = temp;
		//准备下一次循环
		m = i;
	}
}

}
void HeapSort(int a[], int n){
int i, j;
int temp;
//自下而上构造小根堆（初始堆）
for(i = n / 2 - 1;i &gt;= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点（叶子节点已经满足小根堆，只需要调整所有的非叶子节点），一点小小的优化
	HeapAdjust(a, i, n);
}

printf("初始堆: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

//把每个元素都调整到应该去的位置
for(i = n - 1; i &gt; 0;i--){
	//首尾交换
	temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	//断尾后剩余部分重新调整
	HeapAdjust(a, 0, i - 1);
}

}
main(){
//int a[] = {7, 6, 5, 4, 3, 2, 1};
//int a[] = {1, 5, 6, 4, 3, 2, 7};
int a[] = {1, 2, 3, 4, 5, 6, 7};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("结果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S. The comments remain detailed. Read the code; I'll stay quiet.

4. Summary

Heapsort involves just a few steps: build the heap -> swap root and tail, cut the tail -> repeat step 2 until all tails are cut.

Is there a clearer, more concise description than this?

By now, we have mastered several useful sorting algorithms:

Quicksort, Mergesort, and Heapsort.

So how do we choose among them in practice? Here are the criteria:

If n is small, use insertion sort or simple selection sort. Since direct insertion sort requires more move operations than simple selection sort, selection sort is better when the data record itself is large.
If the sequence is nearly sorted, direct insertion sort or bubble sort can be used.
If n is large, use an algorithm with the lowest time complexity, such as quicksort, heapsort, or mergesort.
- More specifically, quicksort is best when data is randomly distributed (this relates to hardware optimizations for quicksort, as mentioned in previous posts).
- Heapsort requires only one auxiliary space and doesn't suffer from quicksort's worst-case scenarios.
- Both quicksort and heapsort are unstable. If stability is required, use mergesort. You can also combine insertion sort and mergesort: use insertion sort to get sorted fragments, then merge them. This yields a stable result since insertion sort is stable.

Note: I consulted a senior's blog post while developing the "cutting the tail" concept. My thanks to them.

1. Pros and Cons of Heapsort

2. Internal Principles

3. Implementation Details

4. Summary

Comments

Leave a comment