内容简介:Precious time, which cannot be recovered once lost.堆是一种特殊的树(完全二叉树)。本地主要分享了堆的实现原理,基于堆的排序以及堆的几个应用。所有源码均已上传至github:对于每个节点的值都大于等于子树中每个节点值的堆。
Precious time, which cannot be recovered once lost.
堆是一种特殊的树(完全二叉树)。本地主要分享了堆的实现原理,基于堆的 排序 以及堆的几个应用。所有源码均已上传至github: 链接
准备
堆的定义:
- 必须是一个完全二叉树
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
大顶堆:
对于每个节点的值都大于等于子树中每个节点值的堆。
小顶堆:
对于每个节点的值都小于等于子树中每个节点值的堆。
ps:堆化是堆的核心思想,想彻底了解堆排序,只需要学会堆化即可。
实现一个大顶堆(小顶堆的实现在github上)
初始化
从下标1开始存储数据 a[0]相当于一个哨兵
private MinHeap(int capacity) { arrays = new int[++capacity]; size = capacity; count = 0; }复制代码
插入
这里涉及到一个堆化的问题。while循环不断得比较插入的数据和之前堆中的数据大小。满足条件则进行交换。
private void insert(int data) { if (count >= size) return; arrays[++count] = data; int i = count; while (i / 2 > 0 && arrays[i] < arrays[i / 2]) { swap(arrays, i, i / 2); i = i / 2; } }复制代码
删除
为什么堆也叫优先级队列呢,也正因为它也是有线性操作的,删除只能删除堆顶元素。
这是 arrays[1] = arrays[count];是删除堆顶元素前,先取最后一个元素塞入堆顶,然后进行堆化,防止出现 数组空洞 。
private void removeMin() { if (count == 0) return; arrays[1] = arrays[count]; --count; heapify(arrays, count, 1); }复制代码
堆化有两种:自下向上堆化和自上向下堆化。这里以自上向下堆化为例。
private void heapify(int[] arrays, int count, int i) { while (true) { int max = i; if (i * 2 < count && arrays[i] > arrays[i * 2]) max = i * 2; if (i * 2 + 1 <= count && arrays[max] > arrays[i * 2 + 1]) max = i * 2 + 1; if (max == i) break; swap(arrays, i, max); i = max; } }复制代码
交换满足条件的元素
private void swap(int[] arrays, int p, int q) { int temp = arrays[p]; arrays[p] = arrays[q]; arrays[q] = temp; }复制代码
测试代码
public static void main(String[] args) { MinHeap minHeap = new MinHeap(10); for (int i = 10; i > 0; --i) { minHeap.insert(i); } System.out.println("小顶堆:"); minHeap.printAll(); System.out.println("删除堆顶元素后:"); minHeap.removeMin(); minHeap.printAll(); }复制代码
测试结果
堆排序
建堆
先将一个无序数组自上向下堆化,从前往上处理数据变成一个堆。
时间复杂度O(n)
private void buildHeap(int[] arrays, int size) { for (int i = size / 2; i > 0; --i) { heapify(arrays, size, i); } }复制代码
排序
类似于删除堆顶元素,然后再将这个堆(size-1)再堆化,利两两比较,不停的交换元素,以此类推。
时间复杂度O(nlogn)
private void sort() { buildHeap(arrays, count); System.out.println("建堆后:"); printAll(); int i = count; while (i > 1) { swap(arrays, 1, i--); heapify(arrays, i, 1); } }复制代码
测试代码
maxHeap.sort(); System.out.println("排序后:"); maxHeap.printAll();复制代码
测试结果
求一组动态数据集合的最大 Top K
思考
针对静态数据,如何在一个包含 n 个数据的数组中,查找前 K 大数据呢?可以维护一个大小为 K 的小顶堆,顺序遍历数组,从数组中取出取数据与堆顶元素比较。如果比堆顶元素大,我们就把堆顶元素删除,并且将这个元素插入到堆中;如果比堆顶元素小,则不做处理,继续遍历数组。这样等数组中的数据都遍历完之后,堆中的数据就是前 K 大数据了。
topK
这里为了更简便一些,用到了java PriorityQueue (优先队列的完全体)
- 首先声明一个大小为k的优先队列PriorityQueue,然后循环arrays数组,先添加k个数(理解这k个数已经满足要求了)
- 其次在[k+1,arrays.length]这个范围内,开始逐个与小顶堆的堆顶进行比较,满足条件则交换
- 最后将PriorityQueue的数据以此取出即可
offer 添加一个元素并返回true 如果队列已满,则返回false
poll 移除并返问队列头部的元素 如果队列为空,则返回null
peek 返回队列头部的元素 如果队列为空,则返回null
private int[] topK(int[] arrays,int k){ PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k); for (int i = 0; i < arrays.length; i++) { if (priorityQueue.size() < k){ priorityQueue.offer(arrays[i]); }else{ int value = priorityQueue.peek(); if (arrays[i] > value){ priorityQueue.poll(); priorityQueue.offer(arrays[i]); } } } int[] result = new int[k]; int index = 0; while (!priorityQueue.isEmpty()){ result[index++] = priorityQueue.poll(); } return result; }复制代码
测试代码
public static void main(String[] args) { GetTopKArrays getTopKArrays = new GetTopKArrays(); int[] arrays = new int[10]; for (int i = 0; i <10 ; i++) { arrays[i] = i; } System.out.println("一组动态数据:"); getTopKArrays.print(arrays); int k = 3; int[] result = getTopKArrays.topK(arrays,k); System.out.println("前三的数据为:"); getTopKArrays.print(result); } }复制代码
测试结果
求一组动态数据集合的中位数
维护两个堆,一个大顶堆,一个小顶堆。大顶堆中存储前半部分数据,小顶堆中存储后半部分数据,且小顶堆中的数据都大于大顶堆中的数据。
初始化
public Median(int capacity) { maxHeap = new MaxHeap(capacity); minHeap = new MinHeap(capacity); count = 0; }复制代码
插入
- 堆空,插入大顶堆
- data比大顶堆元素大插入小顶堆,否则插入大顶堆
- 如果大顶堆(小顶堆)的数据数量超过了中间值,则需要平衡,移动数据数量多的堆。
private void insert(int data) { ++count; if (maxHeap.count == 0 && minHeap.count == 0) { maxHeap.insert(data); return; } int max = maxHeap.removeMax(); if (data > max) { maxHeap.insert(max); maxHeap.insert(data); } else { maxHeap.insert(max); minHeap.insert(data); } int mid = count / 2; if (maxHeap.count > mid) { moveMaxMin(maxHeap, minHeap, maxHeap.count - mid); } if (minHeap.count > mid) { moveMinMax(maxHeap, minHeap, minHeap.count - mid); } }复制代码
移动
因为这里是基于上面的堆的实现,没有封装彻底,因此手动实现
private void moveMaxMin(MaxHeap maxHeap, MinHeap minHeap, int index) { for (int i = 0; i < index; i++) { int data = maxHeap.removeMax(); minHeap.insert(data); } } private void moveMinMax(MaxHeap maxHeap, MinHeap minHeap, int index) { for (int i = 0; i < index; i++) { int data = minHeap.removeMin(); maxHeap.insert(data); } }复制代码
测试代码
public static void main(String[] args) { int capacity = 10; Median median = new Median(5); for (int i = 1; i < capacity; i++) { median.insert(i); } System.out.println("大顶堆:"); median.maxHeap.printAll(); System.out.println("小顶堆:"); median.minHeap.printAll(); int midNum = median.maxHeap.removeMax(); System.out.println("中位数为:" + midNum); }复制代码
测试结果
end
您的点赞和关注是对我最大的支持,谢谢!
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。