加入收藏 | 设为首页 | 会员中心 | 我要投稿 湘西站长网 (https://www.0743zz.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

排序——堆排序和TopK

发布时间:2023-02-07 12:30:59 所属栏目:大数据 来源:转载
导读: 前言
堆排序与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;
	}
}

(编辑:湘西站长网)

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