堆排序

堆排序

堆的概念

堆作为一种数据结构，其特征为：

• 堆是一棵完全二叉树。对堆的元素从0开始从上至下，从左往右进行编号可以对应数组中的元素。因此根节点总是对应数组第一个元素，最底层最右边的元素总是对应数组最后一个元素。

  根据完全二叉树的结构，对于第i个元素，我们可以写出其父节点和子节点的下标为：

  • 父节点：(i - 1) / 2
  • 左子节点：2 * i + 1
  • 右子节点：2 * i + 2

• 堆的子节点总是不大於或者不小于其父节点的值。不大於父节点的堆称为大顶堆，不小于父节点的堆称为小顶堆。

堆的成形

堆的成形称为"heapify"，对应函数实现为：

void heapify(int arr[], int n, int i) {
	if (i >= n) {
		return ;
	}
	int max = i;
	int left = 2 * i + 1, right = 2 * i + 2;
	if (left < n && arr[max] < arr[left]) {
		max = left;
	}
	if (right < n && arr[max] < arr[right]) {
		max = right;
	}
	if (max != i) {
		swap(arr, max, i);
		heapify(arr, n, max);
	}
}

从代码中可以看到，对某一个非叶节点，比较其与左、右子节点的大小，如果小于其子节点，则与值较大的子节点交换值。然后对交换了值的子节点进行递归调用。

如果有一颗已经是堆的二叉树某一个节点被替换，则直接对这个节点进行"heapify"操作可以使得其重新变成一个堆。

堆的构造

根据无序数组构造一个堆的过程称为堆的构造，其对应函数为：

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

其基本思想就是遍历每一个父节点并进行"heapify"操作，这是一个自底向顶的过程。对于倒数第二层的父节点来说，"heapify"可以直接构造一个完整的堆，当遍历到该父节点的父节点时，如果在进行"heapify"操作时与该父节点进行了交换的操作，则会递归调用heapify()再次对该父节点进行"heapify"操作使得重新成堆。这样遍历完成后整个二叉树就都是一个有序的堆了。

堆排序

对于一个已经成型的堆进行排序就非常简单了，只需要遍历堆中的所有节点，在每次遍历中都将根节点与当前遍历的最后一个节点进行交换，这样就把当前堆的最大值交换到了最后。然后在堆内将最后一个节点割去，重新进行"heapify"操作使得堆再次成型。

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