数据结构-堆及相关算法

什么是堆，堆的特点

一棵完全二叉树，且满足任意节点始终不大于（或者不小于）左右子节点。前者称为最小堆，后者为最大堆。

存储：数组（而不是二叉树）

对于长度为N的数组A中的任意一个元素i（0<=i<N/2），其左右子节点为i*2+1和i*2+2。以大顶堆为例，该堆始终满足：

A[i]>=A[i*2+1] && A[i]>=A[i*2+2]   

常用操作

堆的构造：对于给定的数组和长度，一般都是在数组上就地堆化。

1. 自上而下构建（ShiftUp自下往上调整堆）==》适用于逐渐往数据尾部增加新节点

从0到N构建堆，往数据中添加元素A[i]，使得新的数组A[0..i]满足堆化性质。

自上而下构建堆 向上调整

2. 自下而上构建（ShiftDown自上往下调整堆）==》适用于逐渐删除堆顶节点（将堆顶节点与数据尾元素交换），然后在剩下的节点中寻找最大值的放在堆顶

从数组的最后一个父节点N/2-1开始，递减到0，以每个父节点为线索，逐渐调整该节点的子节点。

自下而上构建堆 向下调整

时间复杂度分析

堆的调整时间复杂度均为O(logn),构建堆的复杂度为O(nlogn)。

典型应用，常见算法

堆排序

以最大堆为例，由于堆顶元素是最大值，在构造好堆之后，每次把堆顶元素与最后一个元素(i从N到0)交换，然后对当前堆顶向下调整堆，使前i-1个元素再次满足堆的特性。N次之后得到一个升序序列。

堆排序

堆化时间复杂度为O(nlogn)，排序时间复杂度为O(nlogn)，总的时间复杂度为O(nlogn)。

LeetCode TOP-K

以下两个算法实现中均用到PriorityQueue，它是JAVA库中基于堆的一个实现类。既实现了队列常用方法，又满足堆的特性，可以很好地解决top-k类问题。

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

For example,

Given [1,1,1,2,2,3] and k = 2, return [1,2].

LeetCode 347

692. Top K Frequent Words

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

LeetCode 692

时间复杂度O(NlogK)。

JAVA中的实现类

PriorityQueue

JAVA集合框架中的一个实现类。

基于堆实现。

PriorityQueue中的元素按自然排序（元素类实现Comparable接口）有序，或者按通过构造函数定义的Comparator排序。

队列头是序列最小值。

非同步，线程不安全。如需同步，请使用PriorityBlockingQueue.

入队出队(offer,poll,remove,add)操作时间复杂度O(logn)。

remove(Object), contains(Objects) 时间复杂度O(n)。

peek, element, size方法O(1)时间。

引用：

https://www.cnblogs.com/eudiwffe/p/6202111.html

https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html