Java堆常用操作及相关leetcode算法题
堆Heap
堆是一种完全二叉树且满足以下条件：
每个节点都大于等于孩子节点，称为最大堆，堆顶元素最大
每个节点都小于等于孩子节点，称为最小堆，堆顶元素最小
判断数据结构的好坏要对比四个操作
1、访问Access
堆没有索引的概念，不存在访问的操作。
2、搜索Search
一般只搜索堆顶元素，时间复杂度为O(1)。
如果要搜索任意元素，时间复杂度为O(N)。
3、插入Insert
插入一个元素，先插入在二叉树的下一个位置，然后比较该元素和父节点，如果大于父节点，进行交换，直到小于父节点为止。因为只需要和父节点做比较，且这是一个二叉树的结构，因此时间复杂度为O(logN)。
设堆中一共有N个节点，第一层1个，第二层2个，…，第m层
2
m
−
1
2^{m-1}
2m−1个。1+2+4+…+
2
m
−
1
2^{m-1}
2m−1=N，使用等比数列的前n项和，2+
2
2
2^{2}
22+
2
3
2^{3}
23+…+
2
m
−
1
2^{m-1}
2m−1=N-1，得出m=
l
o
g
2
(
N
+
1
)
log_2(N+1)
log2(N+1)，则一共有
l
o
g
2
(
N
+
1
)
log_2(N+1)
log2(N+1)层，而新插入的节点只需要和父节点进行比较交换，所以一共需要比较交换
l
o
g
2
(
N
+
1
)
−
1
log_2(N+1)-1
log2(N+1)−1次，时间复杂度为O(logN)。
4、删除Delete
一般删除根节点。删除根节点后，将堆中的最后一个元素移到根节点，保持二叉树的结构。然后再将根节点与子节点比较，满足最大堆或最小堆的要求就不进行移动，否则进行移动，直到整个堆都满足要求位置为止。
比如上面的二叉树，先将1删除，然后7上移到根节点的位置，保持完全二叉树的结构。然后7和子节点比较，和较小的2进行交换，2称为根节点。然后7再和子节点比较，和较小的4交换。就得到了一棵新的完全二叉树。
和插入同理，删除父节点后，最后一个节点移动到父节点的位置，然后和子节点进行比较交换，一共有
l
o
g
2
(
N
+
1
)
log_2(N+1)
log2(N+1)层，需要比较交换
l
o
g
2
(
N
+
1
)
−
1
log_2(N+1)-1
log2(N+1)−1次，时间复杂度为O(logN)。
堆化
时间复杂度为O(N)。
将一组为无序的数转为一棵完全二叉树，然后改造为最大堆或最小堆。
第一步：
一个数组转化为一棵完全二叉树，结构是唯一的。时间复杂度是O(N)，因为要遍历数组。
第二步：
改造为最小堆或最大堆，以最小堆为例。中心思想是将每个节点与它的孩子节点相比较。叶子节点没有孩子，所以不需要比较。然后将上一层的节点与孩子节点比较，如果有孩子节点比它小，与较小的孩子节点进行交换。如果孩子节点都比它大，则该节点与其孩子节点构成了一个最小堆。以此类推，直到构成一个最小堆。
以二叉树的特性来看，高度为0的叶子节点最多有n/2个，而叶子节点没有孩子进行交换，所以与孩子交换的次数是0，相乘得到叶子节点总的交换次数为0。高度为1的节点最多有n/4个，最多交换一次，即与叶子节点交换，相乘得到总的交换次数为n/4，即
n
2
2
∗
1
\frac{n}{2^2} * 1
22n∗1。高度为2的节点最多有n/8个，最多交换两次，即与下面两层的节点交换，相乘得到总的交换次数为n/4，即
n
2
3
∗
2
\frac{n}{2^3} * 2
23n∗2，以此类推，高度为i的节点的总的交换次数为
n
2
i
+
1
∗
i
\frac{n}{2^{i+1}} * i
2i+1n∗i。将每一层的次数相加，
log
2
N
{\log_2N}
log2N是二叉树的高度，
∑
i
=
0
log
2
N
n
2
i
+
1
∗
i
\sum_{i=0}^{\log_2N}\frac{n}{2^{i+1}} * i
∑i=0log2N2i+1n∗i，
提出
n
2
\frac{n}{2}
2n，变为
n
2
∑
i
=
0
log
2
N
i
2
i
\frac{n}{2}\sum_{i=0}^{\log_2N}\frac{i}{2^{i}}
2n∑i=0log2N2ii，将
log
2
N
{\log_2N}
log2N看作
∞
\infty
∞，
∑
i
=
0
log
2
N
i
2
i
\sum_{i=0}^{\log_2N}\frac{i}{2^{i}}
∑i=0log2N2ii收敛于2，于是最终整个式子收敛于N。这一步的时间复杂度也为O(N)。
于是，两步都是O(N)，两步又是顺序关系，最终堆化的时间复杂度为O(N)。
Java堆常用操作
1、创建堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();最小堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());最大堆
2、添加元素
minHeap.add(10);
minHeap.add(8);
minHeap.add(9);
minHeap.add(11);
minHeap.add(2);
System.out.println(minHeap.toString());
[2, 8, 9, 11, 10]
maxHeap.add(10);
maxHeap.add(8);
maxHeap.add(9);
maxHeap.add(11);
maxHeap.add(2);
System.out.println(maxHeap.toString());
[11, 10, 9, 8, 2]
按照堆化的操作，先构造一棵完全二叉树，然后进行父子节点交换。
3、获取堆顶元素
minHeap.peek();
maxHeap.peek();
4、删除堆顶元素
int top = minHeap.poll();
int top = maxHeap.poll();
4、获取堆的元素个数
int num = minHeap.size();
int num = maxHeap.size();
5、堆的遍历
while(!minHeap.isEmpty()) {
int top = minHeap.poll();
}
6、堆相关leetcode
No.215 数组中的第k个最大元素
思路：将数组中的元素放进一个最大堆中，遍历堆k次，取出堆顶元素
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
for(int num : nums) {
heap.add(num);
}
int top = 0;
while(!heap.isEmpty() && k > 0) {
top = heap.poll();
k--;
}
return top;
}
}
No.692 前k个高频单词
思路：将数组中的单词和出现的次数加入哈希表中，创建一个最大堆，重写比较函数Comparator，如果两个单词的出现次数一样，调用compareTo方法按照字母顺序排序；如果出现次数不一样，按照从大到小的顺序排序。将map的keySet加入堆中，然后遍历堆，取出前k个单词，加入集合result，返回result。
class Solution {
public List<String> topKFrequent(String[] words, int k) {
HashMap<String, Integer> map = new HashMap<>();
for(String word : words) {
if(map.containsKey(word)) {
map.put(word, map.get(word) + 1);
} else {
map.put(word, 1);
}
}
PriorityQueue<String> heap = new PriorityQueue<>((o1, o2) -> {
Integer count1 = map.get(o1);
Integer count2 = map.get(o2);
if (count1.equals(count2)) {
//出现次数一样，按照字母顺序排序
return o1.compareTo(o2);
} else {
//按照出现次数从大到小
return count2 - count1;
}
});
List<String> result = new ArrayList<>();
heap.addAll(map.keySet());
while(!heap.isEmpty() && k > 0) {
String top = heap.poll();
result.add(top);
k--;
}
return result;
}
}