排序——堆排序和TopK

前言

堆排序与TopK的问题，面试中还是经常问的，索性也整理一下。下面是徒手写的，供参考.

堆排序思路

堆的数据结构，本身就是一个二叉树，二叉树的每一个根节点始终大于两个叶子的值，这就是大顶堆；如果始终小于两个叶子节点的值，这就是小顶堆。

堆排序的操作方式：先构造一个大顶堆，这样我们就知道了最大的值，然后将最大值和数组的最后一个元素交换，然后重新调整堆，这样我们就确定新堆的最大值（第二大），再和数组的倒数第二个元素进行交换。如此循环，知道全部排好。

构造堆的方式，是利用下沉方法进行的，通过对数组前一半的元素进行下沉即可构造一个堆，因为只有前一半的节点才有子节点。

实现

public void heapSort(int[] array) {
	// 先构造一个大顶堆
	int N = array.length - 1;
	for (int i = (N - 1) / 2; i >= 0; i--) {
		sink(array, i, N);
	}
	// 每次将堆顶元素替换至末尾
	for (int i = N; i > 0; i--) {
		swap(array, 0, i);  // 堆顶元素交换至末尾
		sink(array, 0, i - 1);  // 重新下沉
	}
}
public void sink(int[] array, int k, int tail) {
	while (2 * k + 1 <= tail) {
		int index = 2 * k + 1;
		if (index < tail && array[index] < array[index + 1]) // 大顶堆逻辑
			index = 2 * k + 2;
		if (array[k] >= array[index])
			break;
		swap(array, k, index);
		k = index;
	}
}
public void swap(int[] array, int i, int j) {
	int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

TopK问题思路

创建一个小顶堆，堆的元素个数为 k，然后进行遍历超大数组，每次过来一个元素和堆顶相比，比堆顶小或者等于可以确定非TopK元素，如果比堆顶元素大，则替换堆顶元素，并进行调整堆结构大数据排序，如此循环往复…

实现

public int[] topK(int[] array, int k) {
	int[] res = new int[k];
	// 复制k个元素
	for (int i = 0; i < k; i++) {
		res[i] = array[i];
	}
	// 构造一个小顶堆
	for (int i = (k - 2) / 2; i >= 0; i--) {
		sink(res, i, k - 1);
	}
	
	// 然后遍历array数组，每次和堆顶元素比较，如果大于就替换堆顶并下沉
	for (int i = k; i < array.length; i++) {
		if (array[i] > res[0]) {
			res[0] = array[i];
			sink(res, 0, k - 1);
		}
	}
	return res;
}
public void sink(int[] array, int k, int tail) {
	while (2 * k + 1 <= tail) {
		int index = 2 * k + 1;
		if (index < tail && array[index] > array[index + 1]) // 小顶堆逻辑
			index = 2 * k + 2;
		if (array[k] <= array[index])
			break;
		swap(array, k, index);
		k = index;
	}
}

（编辑：上海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!