堆排序

堆定义

大顶堆：根节点比左右节点都大
小顶堆：根节点比左右节点都小
堆是一颗完全二叉树，所以可以用数组表示。

堆调整

堆调整从父节点开始一直到叶子节点，如：

算法的时间复杂度为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);
   }
}

堆排序

堆排序(从小到大)的规程就是：

1. 将数组调整为大顶堆
2. 将堆对元素同最后一个元素交换

3. 去掉最后一个元素，然后将剩余数组继续调整为大顶堆

   
   

  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;
    }