堆排序

等我考完了再补这个博客的具体内容。

堆排序有如下几个特征

• 堆是一个完全二叉树，构造生存，删除都要按照完全二叉树的规则进行
• 所有父节点的值都必须要大于（或者小于）子结点的值
• 为了方便实现可以用数组模拟代替完全二叉树的构建

对于一颗完全二叉树，在进行模拟的时候，设当前结点为i，则有

• 其父结点parent = (i – 1) / 2
• 其左孩子 left_c = (i * 2) + 1
• 其右孩子 right_c = (i * 2) + 2

堆排序代码，分为，

• heapify堆化，正对一个结点的堆化，
• build_heap，构建堆，将整个数组堆化（批量调用heapify）
• heap_sort，利用堆进行的堆排序

代码如下

#include<stdio.h>

void swap(int arr[], int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

void heapify(int tree[], int n, int i){
	int max = i;
	int c1 = 2 * i + 1;
	int c2 = 2 * i + 2;
	if (c1 < n && tree[c1] > tree[max]) {
		max = c1;
	}
	if (c2 < n && tree[c2] > tree[max]) {
		max = c2;
	}
	if(max != i){
		swap(tree, max, i);
		heapify(tree, n ,max);
	}
}

void build_heap(int tree[], int n){
	int last_node = n - 1;
	int parent = (last_node - 1) / 2;
	int i;
	for (i = parent; i >= 0; i--) {
		heapify(tree, n, i);
	}
}

void heap_sort(int tree[], int n) {
	build_heap(tree, n);
	int i;
	for (i = n - 1; i >= 0; i--){
		swap(tree, i ,0);
		heapify(tree, i, 0);
	}
}

int main(){
	int tree[] = {2, 10, 3, 1, 5, 4};
	int n = 6;
	heap_sort(tree, n);
	
	int i;
	for(i = 0; i < n; i++){
		printf("%d\n",tree[i]);
	}
	return 0;
}