堆排序一般用来快速的选出 第K个最大数之类的问题。
一个堆的定义如下
1 堆是一个二叉树
2 如果所有的节点满足如下的规则，如果节点不为空，如果有左子节点，且左子节点比此节点大，如果有右子节点，且右子节点比此节点大，那么这是个小堆，反之是个大堆。
一般一个堆使用一个数据表示。
如果一个节点是arr[n]，那么其左子节点是arr[2n+1]，右子节点是arr[2n+2]
那么如果对堆进行初始化呢，最重要的点是从哪个节点开始调整(这个是重点)，我们从最后一个非叶子节点开始调整，最后这个非叶子节点的index是 (len-1)/2(其中len是数组的长度)
其算法如下（假设我们是初始化一个大堆）
//第一次的时候，这个index是 (len-1)/2，就是最后一个非叶子节点
private void adjustHeapOfIndexNode(int[] arr,int index,int length){
//找出左孩子节点
int leftC = 2*index+1;
//找出右孩子节点
int rightC = leftC +1;
int mastIndex = index;
//将左孩子节点和右孩子节点中的较大者与index交换
if(leftC < length && arr[leftC] > arr[mastIndex]){
mastIndex = leftC;
}
if(rightC < length && arr[rightC] > arr[mastIndex]){
mastIndex = rightC;
}
// if mastIndex not equals index swap them
if( mastIndex != index){
int temp = arr[mastIndex];
arr[mastIndex]= arr[index];
arr[index] = temp;
// 递归的处理交换后的左孩子节点或是右孩子节点
adjustHeapOfIndexNode(arr,mastIndex,length);
}
}
经过上面的步骤的处理后，index及其子节点已经是一个大堆了，那么只要按照这个方法，将其之前的所有非叶子节点都处理一遍就成了一个大堆，代码如下
//将所有的非叶子节点都处理一遍
private void adjustHeap(int[] arr,int length){
for(int index = (length -1) / 2 ; index >= 0 ; index --){
adjustHeapOfIndexNode(arr,index,length);
}
}
经过上面的处理之后，我们已经建立起来了一个大堆，那么在arr[0就存储着最大的值了，我们将arr的最后一个节点与arr[0]互换，那么接着处理arr的前n-1个数据，继续的使用上面的构造大堆的方法，我们就可以对这个数组进行排序了，代码如下
public void test() throws Exception{
int[] arr = {16,7,3,20,17,8};
for(int length = arr.length;length>0;length--){
adjustHeap(arr,length);
//将上面的大堆的arr[0]与最后一个元素互换，然后接着处理前n-1个数据
int temp = arr[0];
arr[0] = arr[length -1];
arr[length -1] = temp;
}
for(int i = 0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
打印出来的结果如下
3
7
8
16
17
20
如上是整个堆排序的原理和代码，使用堆结构，我们可以构造一个通用的数据结构，比如PriorityQueue，如下
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
private static final long serialVersionUID = -7720805057305804111L;
//默认的堆的大小
private static final int DEFAULT_INITIAL_CAPACITY = 11;
//这个是我们的堆排序里面介绍的数组，用来存储堆数据
transient Object[] queue;
//堆里面元素的个数，说明queue里面可能有些预分配的空间没有存储数据
private int size = 0;
//比较器，如果没有的话，默认使用元素的自然序列比较
private final Comparator<? super E> comparator;
在PriorityQueue构造函数里面会调用一个方法heapify，用来初始化堆
如下
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);
}
具体源码可以参考我的例子，我们看下几个重要的方法，
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;
}
可以看到poll的时候，直接的取第0个元素，然后将剩余的元素继续的调整成一个小堆。
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
siftUp(i, e);
return true;
}
如上在插入数据的时候，也会对数组进行调整。
所以说PriorityQueue的poll个offer方法的时间复杂度都是logN
因为PriorityQueue是非线程安全的，所以jdk里面提供了PriorityBlockingQueue，是堵塞的线程安全的优先队列。
我们再来看延迟队列
public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
implements BlockingQueue<E> {
private final transient ReentrantLock lock = new ReentrantLock();
private final PriorityQueue<E> q = new PriorityQueue<E>();
}
可以认为DelayQueue是优先队列的一个代理的特殊场景，DelayQueue里面的元素都实现了Delayed，按照延迟的时间来生成一个小堆，等于说最先到期的元素排在最前面。
public boolean offer(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
q.offer(e);
if (q.peek() == e) {
leader = null;
available.signal();
}
return true;
} finally {
lock.unlock();
}
}
如上的offer方法直接的调用了q.offer(e)，如果是第一次插入，还需要唤醒堵塞在available等待获取数据的线程。
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
E first = q.peek();
//即使q里面有数据，但是delay的时间没到，也不会返回数据
if (first == null || first.getDelay(NANOSECONDS) > 0)
return null;
else
return q.poll();
} finally {
lock.unlock();
}
}
如上的poll是非堵塞的方法，当然获取lock的时候也会堵塞下，但是发现没有数据会立马的返回。
当然延迟队列也提供了可以被中断的堵塞方法获取数据，如下
public E take() throws InterruptedException {
final ReentrantLock lock = this.lock;
//在获取锁的过程中可以被中断
lock.lockInterruptibly();
try {
for (;;) {
E first = q.peek();
if (first == null)
//如果数据为空，堵塞在available condition上面
available.await();
else {
long delay = first.getDelay(NANOSECONDS);
//如果delay到期，直接的返回
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();
}
}
当然对于延迟任务，我们也可以使用时间轮来实现而不必依赖延迟队列。
网友评论