算法技巧-大小根堆（Max/Min Heap）
站长
· 阅读数 5
堆（Heap）是一种基于完全二叉树的数据结构，用于维护一些元素集合中的最大值或最小值。
基本概念
堆可以分为两种类型：最大堆（Max Heap） 和最小堆（Min Heap）。在最大堆中，每个节点的值都大于或等于其子节点的值；而在最小堆中，每个节点的值都小于或等于其子节点的值。 堆的主要操作包括插入、删除和获取堆顶元素:
- 插入操作是将新元素插入到堆的末尾，然后通过上滤操作将其移动到正确的位置,时间复杂度是
O(log n)。 - 删除操作是将堆顶元素删除，并将堆的最后一个元素移动到堆顶，然后通过下滤操作将其移动到正确的位置，时间复杂度是
O(log n)。 - 获取堆顶元素操作则是返回堆顶元素的值，而不删除它,时间复杂度
O(1)。
一般可使用数组来存储
应用场景
优先队列PriorityQueue
PriorityQueue是Java中的一个优先队列，它使用堆来实现，可以用来维护一组元素的顺序。PriorityQueue中的元素默认按照自然顺序进行排序，也可以使用Comparator来指定排序规则。在PriorityQueue中，插入操作和删除操作的时间复杂度都是O(log n)，获取队头元素的时间复杂度是O(1)。
PriorityQueue的实现基于堆，它可以是最小堆或最大堆。在Java中，默认是最小堆，即队头元素是最小的元素。如果需要使用最大堆，可以通过传入Comparator来指定排序规则。
源码解读
PriorityQueue继承关系如下
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable
关键成员变量
// 默认容量
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 存储元素
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
transient Object[] queue; // non-private to simplify nested class access
// 元素个数
private int size = 0;
// 比较器
private final Comparator<? super E> comparator;
// 修改次数
transient int modCount = 0; // non-private to simplify nested class access
构造器,如果传入的是collection，会通过heapify构造堆
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
public PriorityQueue(PriorityQueue<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initFromPriorityQueue(c);
}
public PriorityQueue(SortedSet<? extends E> c) {
this.comparator = (Comparator<? super E>) c.comparator();
initElementsFromCollection(c);
}
public PriorityQueue(Collection<? extends E> c) {
if (c instanceof SortedSet<?>) {
SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
this.comparator = (Comparator<? super E>) ss.comparator();
initElementsFromCollection(ss);
}
else if (c instanceof PriorityQueue<?>) {
PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
this.comparator = (Comparator<? super E>) pq.comparator();
initFromPriorityQueue(pq);
}
else {
this.comparator = null;
initFromCollection(c);
}
}
// 通过SortedSet初始化，直接copy
private void initElementsFromCollection(Collection<? extends E> c) {
Object[] a = c.toArray();
if (c.getClass() != ArrayList.class)
a = Arrays.copyOf(a, a.length, Object[].class);
int len = a.length;
if (len == 1 || this.comparator != null)
for (int i = 0; i < len; i++)
if (a[i] == null)
throw new NullPointerException();
this.queue = a;
this.size = a.length;
}
// 通过优先队列初始化
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
if (c.getClass() == PriorityQueue.class) {
this.queue = c.toArray();
this.size = c.size();
} else {
initFromCollection(c);
}
}
// 通过Collection初始化
private void initFromCollection(Collection<? extends E> c) {
initElementsFromCollection(c);
heapify();
}
//于对堆进行调整，以满足堆的性质。在PriorityQueue中，堆是通过数组实现的，数组的下标从0开始编号，对于任意下标i，它的左子节点的下标为2i+1，右子节点的下标为2i+2，父节点的下标为(i-1)/2。因此，在对堆进行调整时，需要使用siftDown()方法来维护堆的性质。
private void heapify() {
for (int i = (size >>> 1) - 1; i >= 0; i--)
siftDown(i, (E) queue[i]);
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
入队方法 add(E e)和offer(E e)
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
//扩容
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
//插入元素到数组size的位置，也就是最后一个元素的下一位
//然后，再做自下而上的堆化
siftUp(i, e);
return true;
}
// 扩容数组
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
出队 remove()和poll()
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
使用demo
在Java中，默认是最小堆，即队头元素是最小的元素。如果需要使用最大堆，可以通过传入Comparator来指定排序规则。
public class PriorityQueueTest {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(5);
queue.offer(3);
queue.offer(7);
queue.offer(1);
System.out.println("queue size: " + queue.size());
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}
输出
queue size: 4
1
3
5
7
延迟队列DelayQueue
DelayQueue是Java中的一个线程安全的延迟队列，它实现了BlockingQueue接口，并具有延迟元素删除的功能。DelayQueue中的元素必须实现Delayed接口，该接口包含一个getDelay()方法，该方法返回元素的剩余延迟时间。在DelayQueue中，只有延迟时间到期的元素才能被取出。
DelayQueue的实现基于PriorityQueue，它使用堆来维护延迟元素的有序集合。在DelayQueue中，元素的顺序是由它们的延迟时间来决定的，延迟时间最短的元素在队头，延迟时间最长的元素在队尾。
源码解读
定义
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
implements BlockingQueue<E>
DelayQueue中存储的对象必须是Delayed，赋予了延迟操作的能力，Delayed继承Comparable，因此也要重写compareTo方法
public interface Delayed extends Comparable<Delayed> {
long getDelay(TimeUnit unit);
}
成员变量
// 这个属性是一个可重入锁，用于保护DelayQueue的线程安全。在DelayQueue中，所有修改操作都需要获取这个锁才能执行，以避免多个线程同时修改队列导致的并发问题。
private final transient ReentrantLock lock = new ReentrantLock();
// 这个属性是一个优先队列，用于存储DelayQueue中的元素。
private final PriorityQueue<E> q = new PriorityQueue<E>();
//这个属性是一个指向当前队列中的“领导者”线程的引用。在DelayQueue中，只有“领导者”线程才能执行take()和poll()方法，即从队列中取出元素。当“领导者”线程不可用时，其他线程可以竞争成为新的“领导者”线程。
private Thread leader = null;
//属性是一个条件变量，用于实现线程同步。
private final Condition available = lock.newCondition();
入队
public boolean add(E e) {
return offer(e);
}
public void put(E e) {
offer(e);
}
public boolean offer(E e, long timeout, TimeUnit unit) {
return offer(e);
}
public boolean offer(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
q.offer(e);
//如果新加入的是最小的延迟时间，就重新唤醒一个作为leader去处理
if (q.peek() == e) {
leader = null;
available.signal();
}
return true;
} finally {
lock.unlock();
}
}
出队
//获取DelayQueue的锁，然后调用PriorityQueue的peek()方法获取队头元素，如果队头元素为null或者其过期时间还未到，则返回null，否则调用PriorityQueue的poll()方法将队头元素从队列中移除并返回
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
E first = q.peek();
if (first == null || first.getDelay(NANOSECONDS) > 0)
return null;
else
return q.poll();
} finally {
lock.unlock();
}
}
//按照指定时间获取对头元素
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
long nanos = unit.toNanos(timeout);
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
for (;;) {
E first = q.peek();
if (first == null) {
if (nanos <= 0)
return null;
else
nanos = available.awaitNanos(nanos);
} else {
long delay = first.getDelay(NANOSECONDS);
if (delay <= 0)
return q.poll();
if (nanos <= 0)
return null;
first = null; // don't retain ref while waiting
if (nanos < delay || leader != null)
nanos = available.awaitNanos(nanos);
else {
Thread thisThread = Thread.currentThread();
leader = thisThread;
try {
long timeLeft = available.awaitNanos(delay);
nanos -= delay - timeLeft;
} finally {
if (leader == thisThread)
leader = null;
}
}
}
}
} finally {
if (leader == null && q.peek() != null)
available.signal();
lock.unlock();
}
}
//获取对头元素，直到时间等到
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
lock.lockInterruptibly();
try {
for (;;) {
E first = q.peek();
if (first == null)
available.await();
else {
long delay = first.getDelay(NANOSECONDS);
if (delay <= 0)
return q.poll();
first = null; // don't retain ref while waiting
if (leader != null)
available.await();
else {
Thread thisThread = Thread.currentThread();
leader = thisThread;
try {
available.awaitNanos(delay);
} finally {
if (leader == thisThread)
leader = null;
}
}
}
}
} finally {
if (leader == null && q.peek() != null)
available.signal();
lock.unlock();
}
}
使用demo
class DelayedTask implements Delayed {
private final long delayTime;
private final long expireTime;
public DelayedTask(long delayTime, TimeUnit timeUnit) {
this.delayTime = TimeUnit.MILLISECONDS.convert(delayTime, timeUnit);
this.expireTime = System.currentTimeMillis() + this.delayTime;
}
@Override
public long getDelay(TimeUnit unit) {
return unit.convert(expireTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
@Override
public int compareTo(Delayed o) {
return Long.compare(this.getDelay(TimeUnit.MILLISECONDS), o.getDelay(TimeUnit.MILLISECONDS));
}
}
public class DelayQueueTest {
public static void main(String[] args) throws InterruptedException {
DelayQueue<DelayedTask> delayQueue = new DelayQueue<>();
delayQueue.add(new DelayedTask(5, TimeUnit.SECONDS));
delayQueue.add(new DelayedTask(10, TimeUnit.SECONDS));
delayQueue.add(new DelayedTask(3, TimeUnit.SECONDS));
System.out.println("delayQueue size: " + delayQueue.size());
Thread.sleep(2000);
while (!delayQueue.isEmpty()) {
System.out.println(delayQueue.take().getDelay(TimeUnit.SECONDS));
}
}
}
算法题
347 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2:
输入: nums = [1], k = 1 输出: [1]
提示：
1 <= nums.length <= 105 k 的取值范围是 [1, 数组中不相同的元素的个数] 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
实现方法
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
}
应用场景
Top K 问题
在一组元素中找到前K个最大或最小的元素。可以使用一个小根堆来维护前K大的元素，或者使用一个大根堆来维护前K小的元素。
数据流中的第K大元素
在一个不断变化的数据流中找到第K大的元素。可以使用一个小根堆来维护前K大的元素，每次加入新元素时，如果小根堆的大小小于K，则直接将元素插入堆中；否则，如果新元素比小根堆中最小的元素大，则将最小元素替换为新元素，然后重新调整堆。
最小的K个数
在一个整数数组中找到最小的K个数。可以使用一个大根堆来维护当前找到的最小K个数，每次加入新元素时，如果大根堆的大小小于K，则直接将元素插入堆中；否则，如果新元素比大根堆中最大的元素小，则将最大元素替换为新元素，然后重新调整堆。
合并K个排序链表
将K个已经排好序的链表合并成一个有序链表。可以使用一个小根堆来存储每个链表的头结点，每次从堆中取出最小的头结点，将其加入结果链表，并将其后继节点插入堆中。
数据流中的中位数
在一个不断变化的数据流中找到中位数。可以使用一个大根堆和一个小根堆来维护当前的中位数，其中大根堆存储前半部分较小的元素，小根堆存储后半部分较大的元素。每次加入新元素时，如果两个堆的大小相同，则将元素插入小根堆中；否则，如果小根堆的大小比大根堆大1，则将小根堆中最小的元素插入大根堆中，然后将新元素插入小根堆中。这样，中位数就是大根堆的堆顶元素或者两个堆顶元素的平均值。