- 堆
- 一、概念与分类
- 二、现实生活中的应用
- 1. 病人手术排期
- 2. 操作系统的任务调度
- 三、时间复杂度
- 四、二叉堆
- 最大堆
- 代码实现
- 最小堆
- 最小堆转最大堆
- LeetCode TopK问题
- leetcode 面试题17.14 最小的k个数
- leetcode 347 频率最高的k个数
- leetcode 373 最小的k个数对
- 堆排序
堆即优先级队列。按照优先级的大小动态出队。元素个数动态变化。
堆分为:二叉堆(应用最广泛)、d叉堆、索引堆
二、现实生活中的应用 1. 病人手术排期病情相同的情况下,先来的病人排在前面,若临时来了个病人病情较重,优先安排手术。而要排手术的病人是不确定的,动态变化的。
相比普通排序,最大的区别是排序的元素个数是确定的,不会发生变化。
2. 操作系统的任务调度CPU和内存资源有限,当资源不够用时,会先执行优先级较高的任务(通常系统任务的优先级高于普通应用)。而任务数量是不定的,随时有可能开启新任务或关闭旧任务。
三、时间复杂度| 入队 | 最大值出队 | |
|---|---|---|
| 普通链式队列 | O(1),一个个尾入 | O(N),遍历队列,找到最大值 |
| 优先级队列(堆) | O(logN) | O(logN) |
四、二叉堆O(logN)的时间复杂度通常和“树”结构相关。但并非要实际构造一棵树,而是算法逻辑上的树结构。
归并排序的递归过程也是一棵“递归树”。时间复杂度为O(NlogN)。
二叉堆基于完全二叉树实现。只有完全二叉树适用数组存储元素,不会浪费空间用于存储空结点。其他二叉树都使用链式结构。
由于二叉堆使用数组存储,故结点编号可对应数组索引,从0开始。
最大堆中只能确定根结点是最大值,子树中并非上层结点就一定大于下层结点。
代码实现基于动态数组ArrayList实现的最大堆:
//最大堆,基于动态数组ArrayList实现
public class MaxHeap {
//实际存储堆元素的数组(基于动态数组实现的List接口)
private List elementData;
//当前堆中元素个数
private int size;
public MaxHeap(int size) {
//使用动态数组存放元素
elementData = new ArrayList<>(size);
}
public MaxHeap() {
this(20);
}
private int parent(int k) {
return (k - 1) >> 1;
}
private int leftChild(int k) {
return (k << 1) + 1;
}
private int rightChild(int k) {
return (k << 1) + 2;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void add(int val) {
//往数组末尾添加元素
elementData.add(val);
size++;
//上浮数组尾元素至合适位置,调整为大根堆
siftUp(size - 1);
}
private void siftUp(int k) {
//循环上浮直到无需上浮:1.已经上浮到根结点 2.已满足“当前结点<父结点” 【条件1必须先满足,防止发生数组越界】
while (k > 0 && elementData.get(k) > elementData.get(parent(k))) {
//交换当前结点和父结点
swap(k, parent(k));
//更新索引,继续上浮
k = parent(k);
}
}
private void swap(int k, int parent) {
Integer childVal = elementData.get(k);
Integer parentVal = elementData.get(parent);
//集合覆盖实现交换
elementData.set(k, parentVal);
elementData.set(parent, childVal);
}
public int extractMax() {
//堆为空,抛异常
if(isEmpty()) {
throw new NoSuchElementException("heap is empty! cannot extract!");
}
//堆不为空,堆顶元素即最大值
int max = elementData.get(0);
//将堆尾元素顶到堆顶,覆盖堆顶元素(实现删除)
elementData.set(0, elementData.get(size - 1));
//删除堆尾元素,否则堆中会出现两个相同元素
elementData.remove(size - 1);
size--;
//从堆顶开始下沉,重新调整为大根堆
siftDown(0);
return max;
}
private void siftDown(int k) {
//若还存在子树,则循环下沉调整
while(leftChild(k) < size) {
//左右子树较大值的索引,初始化左子树为较大值
int j = leftChild(k);
//判断右子树是否是最大值:右子树存在 && 右子树大于左子树
if(j + 1 < size && elementData.get(j + 1) > elementData.get(j)) {
j++; //更新较大值索引为右子树
}
//判断左右子树的较大值是否比当前树根大
if(elementData.get(j) > elementData.get(k)) {
swap(k, j); //下沉当前树根
k = j;
}else {
break; //当前树根更大,不下沉
}
}
}
public int peekMax() {
//查询前先判空
if(isEmpty()) {
throw new NoSuchElementException("heap is empty! cannot peek!");
}
return elementData.get(0); //堆顶即最大值
}
public MaxHeap(int[] arr) {
//构造新堆,存放元素
elementData = new ArrayList<>(arr.length);
for(int i : arr) {
elementData.add(i);
size++;
}
//从最后一个非叶子结点开始向上循环执行下沉操作,调整为最大堆
for(int i = parent(size - 1); i >= 0; i--) {
siftDown(i);
}
}
public String toString() {
return elementData.toString(); //List集合已经覆写了toString()方法
}
}
最小堆
最小堆中只能确定根结点是最小值,子树中并非上层结点就一定小于下层结点。
JDK中的优先级队列PriorityQueue默认采用最小堆实现。
最小堆转最大堆实现比较器接口Comparator进行倒序比较。
QueueLeetCode TopK问题 leetcode 面试题17.14 最小的k个数queue = new PriorityQueue<>(new Comparator () { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; //倒序比较 } });
public class Interview1714_TopKSmallestNum {
public int[] smallestK(int[] arr, int k) {
//返回的结果数组
int[] ret = new int[k];
//边界条件
if(arr.length == 0 || k == 0) { //防止queue空指针异常
return ret; //返回空数组
}
//遍历原数组,将前k个数默认存入最大堆
//JDK默认的优先级队列是基于最小堆的,需改造成最大堆
Queue queue = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1; //倒序比较
}
});
//遍历原数组
for(int i = 0; i < arr.length; i++) {
//前k个数默认入堆
if(i < k) {
queue.offer(arr[i]);
}else { //后面的数依次与当前堆顶(最大值)进行比较
int max = queue.peek();
//小于堆顶则覆盖堆顶
if(arr[i] < max) {
queue.poll();
queue.offer(arr[i]);
}
//大于堆顶则说明大于堆中的所有元素,直接跳过
}
}
//此时队列中即保存了k个最小值,依次出队即可
int i = 0;
while(!queue.isEmpty()) {
ret[i++] = queue.poll();
}
return ret;
}
}
leetcode 347 频率最高的k个数
//自定义键值对类 class QueueEntry implements Comparableleetcode 373 最小的k个数对{ int key; //元素值 int value; //元素出现的频率 public QueueEntry(int key, int value) { this.key = key; this.value = value; } public int getKey() { return key; } public int getValue() { return value; } //自定义条件比较,频率高的对象大 ==> 正序比较 @Override public int compareTo(QueueEntry o) { return this.value - o.value; //正序比较 } } public class No347_TopKFreqNum { public int[] topKFrequent(int[] nums, int k) { //返回的结果数组,k个元素值 int[] ret = new int[k]; //边界条件 if(nums.length == 0 || k == 0) { //防止queue空指针异常 return ret; //返回空数组 } //将原数组中的元素及其频率转存到Map集合中 [1,1,1,2,2,3] -> {{1:3},{2:2},{3:1}} Map map = new HashMap<>(); for(int i : nums) { if(!map.containsKey(i)) { //第一次出现的元素直接加入map集合,记录初始频率为1 map.put(i, 1); }else { //重复出现的元素覆盖频率值 int freq = map.get(i); //根据键获取值 map.put(i, freq + 1); } } //遍历map集合的每个键值对,将频率最高的前k个键值对对象放入优先级队列(最小堆) Queue queue = new PriorityQueue<>(); //JDK默认的优先级队列为最小堆 for(Map.Entry entry : map.entrySet()) { //将所有键值对提取出来存放到set集合中,用于遍历 //前k个键值对对象默认入队 if(queue.size() < k) { queue.offer(new QueueEntry(entry.getKey(), entry.getValue())); }else { //后面的键值对对象若大于堆顶,则覆盖堆顶 if(entry.getValue() > queue.peek().getValue()) { queue.poll(); queue.offer(new QueueEntry(entry.getKey(), entry.getValue())); } //小于堆顶则一定小于堆中所有的键值对对象,直接跳过 } } //此时队列中存放的即为前k个频率最高的键值对对象,依次出队,取其键存入结果数组中即可 int i = 0; while (!queue.isEmpty()) { ret[i++] = queue.poll().getKey(); //键为元素值 } return ret; } }
public class No373_TopKPairsSumSmallest {
public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//返回的结果二维数组
List> ret = new ArrayList<>();
//题目已排除边界情况,无需考虑
//JDK默认提供的是最小堆,需转换成最大堆 ==> NumPair类需实现倒序的比较器,也确保下方的offer操作正常执行
Queue queue = new PriorityQueue<>((o1, o2) -> (o2.num1 + o2.num2) - (o1.num1 + o1.num2)); //倒序
//遍历两个升序数组,仅需分别遍历前k个即可组成包含结果中k个最小数对的所有可能数对,为每个数对创建一个对象
for(int i = 0; i < Math.min(nums1.length, k); i++) { //数组长度可能小于k
for(int j = 0; j < Math.min(nums2.length, k); j++) {
NumPair numPair = new NumPair(nums1[i], nums2[j]);
//前k个数对默认入队
if (queue.size() < k) {
queue.offer(numPair);
} else { //后面的k个数对小于堆顶则覆盖堆顶,由优先级队列的offer操作自动重新调整为最大堆
if ((nums1[i] + nums2[j]) < (queue.peek().num1 + queue.peek().num2)) {
queue.poll(); //当前堆顶数对出队
queue.offer(numPair); //新数对入队
} else {
break; //找到一个大于堆顶的则后面的数对一定大于堆顶(数组升序),直接break
}
}
}
}
//此时队列中存放的即为前k个和最小的数对对象,依次出队,取其值存入结果数组
while (!queue.isEmpty()) {
NumPair numPair = queue.poll();
List list = new ArrayList<>();
list.add(numPair.num1);
list.add(numPair.num2);
ret.add(list);
}
//队列为最大堆,出队的序列为降序,需反转为升序
Collections.reverse(ret);
return ret;
}
}
//数对对象
class NumPair {
int num1;
int num2;
public NumPair(int num1, int num2) {
this.num1 = num1;
this.num2 = num2;
}
}
堆排序
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[] {12,2,4,65,34,7,89,3,0,45,39};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
// 1.初始化最大堆
for(int i = (arr.length-1-1)/2; i >= 0; i--) {
siftDown(arr, i, arr.length);
}
// 2.循环交换堆顶和未排序的堆尾元素,每次都让堆顶的最大值到达其排序后的最终位置,并重新调整为最大堆
for(int i = arr.length-1; i > 0; i--) { //最后一个元素已为最大值,无需排序 ==> 循环条件 i>0
//arr[i]即为当前未排序堆中的最后一个元素
swap(0, i, arr);
siftDown(arr,0, i);
}
}
private static void siftDown(int[] arr, int i, int length) {
//只要还有子树,就可以循环下沉调整
while(2 * i + 1 < length) { //数组从0开始编号:左孩子结点 2*i+1
// 1.先找出左右孩子中较大者
int j = 2 * i + 1; //初始默认左孩子为较大者
if(j + 1 < length && arr[j+1] > arr[j]) { //右孩子存在且右孩子较大
j = j + 1;
}
// 2.再比较当前根结点是否小于左右孩子的较大者,小于则下沉,大于则不下沉
if(arr[i] < arr[j]) {
swap(i, j, arr);
i = j;
}else {
break;
}
}
}
private static void swap(int i, int j, int[] arr) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}



