堆和堆排序_c语言

堆Heap

• 必须是完全二叉树
• 父节点大于两个子节点任意一个 （一般大顶堆）

堆的结构：父节点和两个子节点的最值存在于父节点，然后叔叔节点和父节点和爷爷节点的最值存在于爷爷节点处，由于这个特殊的构造，可以很方便地获得最值，大顶堆方便获取最大值，小顶堆方便获取最小值。

当堆中的某一个元素变更时，可以快速通过下沉的或者上浮的方式来重新形成堆，当堆顶元素变更时，它只有一个方向:下沉。每次堆顶与最后一个元素交换，然后堆顶的更新值下沉（去除最后已经交换的部分），形成新的堆,循环往复就是堆排序，类似于选择排序，但是其比选择排序更加容易获得最值，复杂度为O(n*logN)

堆和数组索引关系映射

一种方式(参考):

swap/交换

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

heapify/下沉操作

void heapify(int tree[],int n,int i){
	if(2 * i + 1 > n-1){ //保证至少有一个左子节点，继续 
		return;
	}
	int c1 = 2 * i + 1; // 左 
	int c2 = 2 * i + 2; // 右
	int max;
	if(c2 <= n-1){
		// 取左右最大的 
		max = tree[c2] > tree[c1] ? c2:c1;
	}else{
		max = c1;
	}
	if(tree[i] < tree[max]){ // 可以下沉 
		swap(tree,i,max); 
		heapify(tree,n,max);
	}
}

build_heap/数组建堆

void build_heap(int tree[],int n){
	// 由小堆到大堆去建立，每次都保证只有一个元素不合规，下沉
	// heapify()这个元素即可得到正确的堆 
	int last_node = n - 1;
	int parent = (last_node - 1) / 2;
	int i;
	for(i = parent; i >= 0; i--){
		heapify(tree,n,i);
	}
}

heap_sort/堆排序

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

main测试

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