堆定义
大顶堆:根节点比左右节点都大
小顶堆:根节点比左右节点都小
堆是一颗完全二叉树,所以可以用数组表示。
堆调整
堆调整从父节点开始一直到叶子节点,如:
算法的时间复杂度为O(lgn)
void heapify(int a[], int parent, int heapSize) {
int left = 2 * parent + 1;
while(left < heapSize) {
int maxIdx = parent;
int right = left + 1;
if(left < heapSize && a[left] > a[maxIdx]) {
maxIdx = left;
}
if(right < heapSize && a[right] > a[maxIdx]) {
maxIdx = right;
}
if(maxIdx == parent) break;
int tmp = a[maxIdx];
a[maxIdx] = a[parent];
a[parent] = tmp;
parent = maxIdx;
left = 2 * parent + 1;
}
}
建堆
如果数组元素已经固定,那么可以基于heapify
方法将数组调整为堆结构。过程就是从最右的非叶节点一直heapify
根节点即可,复杂度O(n)
void buildMaxHeap(int a[]) {
if(a == null || a.length <= 1) return;
int heapSize = a.length;
for(int i = heapSize / 2; i >= 0; i--) {
heapify(a, i, heapSize);
}
}
堆排序
堆排序(从小到大)的规程就是:
- 将数组调整为大顶堆
- 将堆对元素同最后一个元素交换
-
去掉最后一个元素,然后将剩余数组继续调整为大顶堆
static void heapSort(int a[]) {
int heapSize = a.length;
for(int i = heapSize / 2; i >= 0; i--) {
heapify(a, i, heapSize);
}
for(int i = heapSize - 1; i >= 0; i--) {
int temp = a[i];
a[i] = a[0];
a[0] = temp;
heapify(a, 0, i);
}
}
第K大数
https://leetcode.cn/problems/kth-largest-element-in-an-array/
// O(nlgn)
static int findKthLargest(int[] nums, int k) {
if(nums == null || nums.length <= k) return -1;
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> {return b - a;});
for(int i = 0; i < nums.length; i++) {
priorityQueue.add(nums[i]);
}
for(int i = 0; i < k - 1; i++) {
priorityQueue.poll();
}
return priorityQueue.poll();
}
// O(nlgk)
static int findKthLargest2(int[] nums, int k) {
if(nums == null || nums.length <= k) return -1;
// 维护一个大小为k的小顶堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for(int i = 0; i < nums.length; i++) {
if(priorityQueue.size() < k) {
priorityQueue.add(nums[i]);
} else {
if(nums[i] > priorityQueue.peek()) {
priorityQueue.poll();
priorityQueue.add(nums[i]);
}
}
}
return priorityQueue.poll();
}
合并 K 个升序链表
https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/307351/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
两个有序链表归并只需要用p
、q
两个指针即可,一个指向链表1,一个指向链表2,然后选择p
、q
中较小的一个往后滑动即可。K个链表归并那就需要大小为k小顶堆来输出最小元素即可
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null) return null;
ListNode dummy = new ListNode();
ListNode p = dummy;
PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>((a, b) -> {
return a.val - b.val;
});
for(ListNode node : lists) {
if(node != null) {
queue.add(node);
}
}
while(!queue.isEmpty()) {
ListNode node = queue.poll();
p.next = node;
p = p.next;
if(node.next != null) {
queue.add(node.next);
}
}
return dummy.next;
}