堆排序及从10亿个数据中找出最小或最大的10个数
高频面试题目
一、堆排序
1、基础知识
* ------基本知识：
* 1. 堆数据结构特征:
* 大顶堆:所有父节点大于等于左右子节点,arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2];
* 大顶堆:所有父节点小于等于左右子节点,arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2];
* 大顶堆只能保证顶元素时最大的,无法保证整个堆(数组)是有序的,小顶堆同理。
* 2. 索引规律：
* 最后一个非叶子节点:N/2-1;
* 父节点i,则左子节点2*i+1,右子节点2*i+2;
* 3. 堆与树的区别
* ①堆占用空间较少;
* 树结构需要存储左右节点指针,占用空间较多;堆仅使用数组;
* ②二叉搜索树与堆
* 二叉搜索树整体都是有序的,搜索很快(logN),插入或删除元素时需要保持平衡,复杂度会超过;
* 使用堆的主要目的是将最大值或最小值放在最前面,从而快速地进行插入和删除操作。
* -----------------------------------------------------------------
* 2021-02-22 17:20:20
* 堆排序的过程包括两部分(升序)：构建大顶堆+交换元素调整堆;
* 其中核心操作就是adjustHeap;
* S1:构建大顶堆:从下往上遍历所有非叶子节点,调整堆;
* S2:构建大顶堆之后,保证顶元素最大,交换顶元素与末尾元素,再次调整堆(堆长度减1)。
* 关键方法：adjustHeap调整堆方法,adjustHeap(int[] arr, int rootIndex, int len).
* -----------------------------------------------------------------
* adjustHeap方法功能：
* 当前节点及之下的节点满足父节点大于等于左右子节点,但是改变了当前节点的值，
* 此时当前节点可能会小于左右子节点，因此需要将调整堆,使其再恢复大顶堆特征。
* adjustHeap方法思路：
* ①当前节点是叶子节点,即2*i+1>=len,则直接退出;
* ②找到左右子节点的较大者;
* ③若当前节点小于较大子节点,则交换;当前子节点值发生改变，则需要递归或循环执行①②。
* 若当前节点大于较大子节点，方法结束。
* -----------------------------------------------------------------
* 如何构建大顶堆或小顶堆(堆的初始化)?
* adjustHeap方法本来是在大顶堆已经建立的基础上，调整堆的，而大顶堆的初始化是通过从下而上，
* 对每一个非叶子节点都执行一次adjustHeap,因此后一次调用在前一次执行的基础之上，因此满足adjustHeap的条件，
* 最后是调整顶节点，因此最终完成大顶堆的初始化。
* 具体实现过程： 依次从最后一个非叶子节点向上遍历，进行调整；
* 假如节点个数为N，则最后一个非叶子节点序号为N/2-1,即N/2个非叶子节点，
* 也就是需要调用N/2次adjustHeap方法；从N/2-1到0.
* ------------------------------------------------------------------
* 升序采用大顶堆,降序采用小顶堆,为什么？
* 答:大顶堆的顶元素最大,将顶元素交换到末尾,满足升序;
* 小顶堆的顶元素最小,将顶元素交换到末尾,满足降序;
* PS:保证堆的下标规律，因此将最大值或最小值转移到最后。
* ------------------------------------------------------------------
* 堆排时间复杂度分析：最好、最坏、平均都是N*logN；
* 仔细分析：堆排核心依赖都是adjustHeap方法，一次堆调整adjustHeap复杂度为O(logN),
* 构建大顶堆调用N/2次adjustHeap,复杂度为(N/2)logN=O(N*logN);
* 交换元素调整堆需要N-2次adjustHeap;因此堆排复杂度为O(N*logN);
*
* 堆排序
* Date:2018-11-09 22:35
* 堆排序的主要思想：
* 根据大顶堆的特点，堆的顶元素为整个堆的最大值，因此，首先就是构建大顶堆，
* 然后循环执行：将顶元素与有效堆的最后一个元素交换，再次调整堆；
* 注意：循环一次，堆的长度减1，因为堆顶元素移动最后，最后一个元素不参与下次堆的调整。
* adjustHeap方法功能：
* ------------------------------------------------------------------------
* 为什么最后一个叶子节点的序号肯定为N/2-1呢？
* 证明：因为堆是一个完全二叉树，父节点的编号为i，则左子节点为2*i+1，右子节点为2*i+2。
* 假设最后一个非叶子节点的编号为k，则其要么只有左子节点，要么左、右子节点都有。
* ①只有左子节点：左子节点编号为2*k+1,此时N=2*k+1+1;那么N/2-1 = k；
* ②左右子节点都存在：右子节点编号为2*k+2,此时N=2*k+2+1，那么N/2-1 = k;
* 综合①和②，N/2-1=k正好是最后一个非叶子节点的编号。
*/
类：HeapSort：
/**
* 堆排序heapSort
*/
public void heapSort(int[] arr) {
//1.构建大顶堆：从第一个非叶子结点从下至上调整堆结构
int notLeaf = arr.length / 2 - 1;
while (notLeaf >= 0) adjustHeap(arr, notLeaf--, arr.length);
System.out.println("大顶堆初始化后:" + Arrays.toString(arr));
//2.交换堆顶元素与末尾元素并调整堆结构
for (int heapLen = arr.length; heapLen > 1; heapLen--) {
swap(arr, 0, heapLen - 1);//将堆顶元素与末尾元素进行交换
adjustHeap(arr, 0, heapLen - 1);//重新对堆进行调整
}
} /**
* 使用场景及功能:顶节点值发生改变,不一定大于子节点,找到该顶节点值合适的位置,置入即可;
* 步骤：
* S1: 比较左右子节点,找到较大值;
* S2: 将较大值填入root位置,并更新root值和index值;
* S3: while循环执行S1、S2,直到遇到叶子节点(即左子节点下标大于等于len);
* S4: 记得最后将rootVal设置到root位置上。
*/
public void adjustHeapMaxTop(int[] arr, int root, int len) {
int index = root * 2 + 1;
if (index >= len) return;
int rootVal = arr[root];//根值
while (index < len) {
//找出左右子节点的最大值(避免交换两次)
if (index + 1 < len && arr[index + 1] > arr[index]) index++;
if (rootVal >= arr[index]) break;//根节点值大于等于子节点值,结束
arr[root] = arr[index];//利用swap交换root和index也可以,不过有点冗余,index位置可能会多次覆盖
root = index;
index = index * 2 + 1;
}
arr[root] = rootVal;//若while循环中调用swap,则该操作可省略
}/**
* 小顶堆
*/
public void adjustHeapMinTop(int[] arr, int root, int len) {
int index = root * 2 + 1;
if (index >= len) return;
int rootVal = arr[root];//根值
while (index < len) {
//找出左右子节点的最大值(避免交换两次)
if (index + 1 < len && arr[index + 1] < arr[index]) index++;
if (rootVal <= arr[index]) break;//根节点值大于等于子节点值,结束
arr[root] = arr[index];//利用swap交换root和index也可以,不过有点冗余,index位置可能会多次覆盖
root = index;
index = index * 2 + 1;
}
arr[root] = rootVal;//若while循环中调用swap,则该操作可省略
}/**
* 递归方式
*/
public void adjustHeapMaxTopRecursive(int[] arr, int root, int len) {
int index = root * 2 + 1;//左子节点
if (index >= len) return;
//找出左右子节点的最大值(避免交换两次)
if (index + 1 < len && arr[index + 1] > arr[index]) index++;
if (arr[root] >= arr[index]) return;//根节点值大于等于左右子节点值,结束
swap(arr, root, index);//交换
adjustHeapMaxTopRecursive(arr, index, len);
} /**
* 交换数组中的两个元素
*/
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}//测试
@Test
public void test() {
int[] arr = {-2, 100, 9, 8, 7, 6, 11, 5, 4, 3, 2, 1};
System.out.println("排序前:" + Arrays.toString(arr));
heapSort(arr);//堆排
System.out.println("排序后:" + Arrays.toString(arr));
}输出结果：
排序前:[-2, 100, 9, 8, 7, 6, 11, 5, 4, 3, 2, 1]
大顶堆初始化后:[100, 8, 11, 5, 7, 6, 9, -2, 4, 3, 2, 1]
排序后:[-2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 100]
二、找出最小的或最大的10个数
/**
* 从10亿个数中找出最小的或最大的10个数
* 思路：找出最小的10个数
* 采用大顶堆。
* S1: 首先构建长度为10的大顶堆;
* S2: 不断地从10亿个数据中读取,
* 若大于等于顶元素,则丢弃;
* 若小于顶元素,则替换顶元素,并调整堆adjustHeap。
*/
public int[] findMin10Nums(int[] arr) {
if (arr == null || arr.length < 10) return Arrays.copyOf(arr, arr.length);
//构建长度为10的大顶堆
int[] res = Arrays.copyOf(arr, 10);
int notLeaf = res.length / 2 - 1;
while (notLeaf >= 0) adjustHeapForMaxTop(res, notLeaf--, res.length);
//遍历读取每一个数值
for (int j = 10; j < arr.length; j++) {
if (arr[j] >= res[0]) continue;//大于顶元素(最大值)
res[0] = arr[j];
adjustHeapForMaxTop(res, 0, res.length);
}
return res;
}
/**
* 与寻找最小10个数对应
*/
public int[] findMax10Nums(int[] arr) {
if (arr == null || arr.length < 10) return Arrays.copyOf(arr, arr.length);
//构建长度为10的大顶堆
int[] res = Arrays.copyOf(arr, 10);
int notLeaf = res.length / 2 - 1;
while (notLeaf >= 0) adjustHeapForMinTop(res, notLeaf--, res.length);
//遍历读取每一个数值
for (int j = 10; j < arr.length; j++) {
if (arr[j] <= res[0]) continue;//大于顶元素(最大值)
res[0] = arr[j];
adjustHeapForMinTop(res, 0, res.length);
}
return res;
}
//调整堆--复用堆排的adjustHeap方法(大顶堆)
public void adjustHeapForMaxTop(int[] arr, int root, int len) {
HeapSort heapSort = new HeapSort();
heapSort.adjustHeapMaxTop(arr, root, len);
}
//调整堆--复用堆排的adjustHeap方法(小顶堆)
public void adjustHeapForMinTop(int[] arr, int root, int len) {
HeapSort heapSort = new HeapSort();
heapSort.adjustHeapMinTop(arr, root, len);
}
/******************************测试******************************/
@Test
public void test() {
int[] arr = {-2, 100, 9, -8, 7, 6, 11, 5, 4, 3, 2, 1, 32, 4, 56, 67, 44, 23, 54, 34, 23, 234, 65, 34, 1, 0, 5, 0, 6, -23, 1004, 1024, 8989};
int[] min10Nums = findMin10Nums(arr);
System.out.println("最小的10个数:" + Arrays.toString(min10Nums));
int[] max10Nums = findMax10Nums(arr);
System.out.println("最大的10个数:" + Arrays.toString(max10Nums));
}
输出结果：
最小的10个数:[4, 3, 2, 0, -2, 1, 1, -8, 0, -23]
最大的10个数:[44, 54, 65, 56, 1004, 234, 1024, 67, 100, 8989]