堆排序和堆能够解决的问题

堆排序

堆的构建过程

了解堆排序前我们需要了解堆的构建的两种方式:

  • 自顶向下
  • 自底向上
  • 自底向上构建堆是通过对每个非叶子节点进行下沉操作(如果节点违反了堆性质,则与其子节点交换直到恢复堆性质)来实现的,通常用于一次性将一个无序数组转换成堆。

假设有一个无序数组 [4, 10, 3, 5, 1],我们想将其构建为一个最大堆。

例子

  1. 最后一个非叶子节点是10(索引为1),其子节点是3和5。
  2. 将10与其子节点中的最大值5比较,因为10已经大于5,不需要交换。
  3. 接下来看第一个节点4(索引为0),其子节点是10和3。
  4. 将4与其子节点中的最大值10比较,因为10大于4,所以交换两者的位置,得到 [10, 4, 3, 5, 1]
  5. 现在,索引为1的节点4成了一个新的子树的根节点,需要再次进行比较和可能的交换,以确保这个子树满足最大堆的性质。不过在这个例子中,4没有子节点,所以这一步可以省略。
  6. 最终得到的最大堆是 [10, 4, 3, 5, 1]
  • 自顶向下构建堆是通过每次插入一个新元素到堆的末尾,然后通过上浮操作(如果节点比父节点大/小,则与父节点交换)来恢复堆的性质,通常用于动态地向堆中添加元素。

例子

  1. 插入4,堆变为 [4]
  2. 插入10,将10放在末尾,得到 [4, 10],然后将10与其父节点4比较,因为10大于4,所以交换两者的位置,得到 [10, 4]
  3. 插入3,放在末尾,得到 [10, 4, 3],3比其父节点4小,不需要交换。
  4. 插入5,放在末尾,得到 [10, 4, 3, 5],5比其父节点4大,进行交换,得到 [10, 5, 3, 4]
  5. 插入1,放在末尾,得到 [10, 5, 3, 4, 1],1比其父节点4小,不需要交换。

最终得到的最大堆是 [10, 5, 3, 4, 1]

时间复杂度区别

我们都知道两者建堆时间复杂度分别为:

  • 自顶向下 O(N * log N)
  • 自底向上 O (log N)

这里贴出一张左程云的图:

image-20240407175455442

可以看到,之所以时间复杂度不同的原因是,当从低开始构建的时候,更多的节点此时只需要从头开始建,时间复杂度更低,越向上节点越少,相反从顶向下则越多节点相对的时间复杂度也越高

代码实现

首先我们实现两种建堆的方法:

  • heapIfy() : 自顶向底
  • heapInsert() : 自底向顶

代码如下:

//向上调整
    public static void heapInsert(int[] arr, int i) {
        while (arr[i] > arr[i - 1] / 2) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    //向下调整
    public static void heapIfy(int[] arr, int i, int size) {
        int l = i * 2 + 1;
        while (l < size) {
            //有左孩子,l
            //右孩子,l+1
            //在左右子节点选择更大的
            int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
            //判断左右节点是否大于其父节点
            best = arr[best] > arr[i] ? best : i;
            //子节点都比当前根节点小
            if (best == i) {
                break;
            }
            //根节点和左右更大的进行交换
            swap(arr, best, i);
            //此时的i就是当前节点下沉调整的新位置
            i = best;
            l = i * 2 + 1;
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tem = arr[a];
        arr[a] = arr[b];
        arr[b] = tem;
    }

区别很明显,从顶向下就是从堆顶开始,判断是否比子节点小,然后交换,从底向上不一样,假设一个节点,加入后,不断和父节点比较,如果大于父节点则交换

最终的排序代码:

public static void heapSort1(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            heapInsert(arr, i);
        }
        int size = n;
        while (size > 1) {
            swap(arr, 0, --size);
            heapIfy(arr, 0, size);
        }
    }

    //从底到顶建立堆
    public static void heapSort2(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            heapIfy(arr,i,n);
        }
        int size = n;
        while (size > 1) {
            swap(arr, 0, --size);
            heapIfy(arr, 0, size);
        }
    }

区别只有建堆的过程,而地下的代码很好理解,其实就是不断的将最后一个堆的元素和堆顶的元素互换,也就是相当于每一次取了一个当前最大的数放在堆底,但是防止这个元素干扰堆的调整,所以要将size–1;

然后从上向下重新构建堆,也就是说两种的时间复杂度都一致,都是O(N log N),这里虽然堆的构建时间复杂度都不一样,但是由于从堆取出最大重新排序,两者一样,所以时间复杂度最终都是一致的。

堆能高效解决的经典问题

在数组中找第K大的元素

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

这道题第一次做使用了快速选择算法,这里我们使用堆算法,在这之前我们看一个例子理解一下堆的解法过程:

假设序列[3,2,3,1, 2 ,4 ,5, 1,5,6,2,3]中,我们需要找第k=4大的数,那么做法就是:

  1. 构造一个大小只有4的小根堆,为什么是小根堆的原因可以参考上一篇结论。(小根堆顶是最大的数)
  2. 堆满了之后,对于小根堆,并一定所有新来的元素都可以入堆的,只有大于根元素的才可以插入到堆中,否则就直接抛弃。这是一个很重要的前提。
  3. 元素进入的时候,先替换根元素,如果发现左右两个子树都小该怎么办呢?很显然应该与更小的那个比较,这样才能保证根元素一定是当前堆最小的。假如两个子孩子的值一样呢?那就随便选一个。
  4. 过程图:

image-20240406102347057

class Solution {
       public int findKthLargest(int[] nums, int k) {
         if(k>nums.length){
            return -1;
        }   
        PriorityQueue<Integer>minHeap = new PriorityQueue<>(k);
        for (int i = 0; i <k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i <nums.length ; i++) {
            Integer peek = minHeap.peek();
            if (peek<nums[i]){
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();

    }
}

理解了过程。这里很好理解,因为Java的优先队列并没有replace方法替代堆顶,所以这里我们先删除,后加入新的符合元素就行。以及这里的优选队列默认实现便是小顶堆

L23 合并 K 个升序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

代码如下,有以下几点需要注意:

  1. 因为并不知道lists[i]是否为null,因此要进行非空判断
  2. 因为dummy虚拟节点会变,所以需要使用一个节点暂存节点
  3. 因为链表第一个是最小的,所以要找最小的元素,使用小根堆(升序用小)
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparing(node -> node.val));
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                queue.add(lists[i]);
            }
        }
        ListNode dummy = new ListNode(-1);
        ListNode tem = dummy;
        while (!queue.isEmpty()) {
            //弹出堆顶最小元素
            dummy.next = queue.poll();
            dummy = dummy.next;
            if (dummy.next != null) {
                queue.add(dummy.next);
            }
        }
        return tem.next;
    }
}

大概流程就是,将三个链表的第一个节点构建为小堆,然后每次对(堆顶)最小的元素取下一个节点加入到堆