从小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692

692.前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2

输出: [“i”, “love”]

解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。

注意，按字母顺序 “i” 在 “love” 之前。

示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4

输出: [“the”, “is”, “sunny”, “day”]

解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，

出现次数依次为 4, 3, 2 和 1 次。

题目来源：力扣（LeetCode）

最下堆排序+哈希表思路

能否写出：不能写出。

时间：1个多小时

思路：

第一次学习最小堆堆排序，前一篇是最大堆排序

从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215

堆排序介绍

堆排序是一种基于最小堆（Min Heap）数据结构的排序算法，它利用最小堆的性质进行排序。最小堆是一种特殊的二叉树，它满足以下两个性质：

最小堆性质：对于堆中任意节点 i，其父节点的值小于等于它的值，即 heap[parent(i)] <= heap[i]。

完全二叉树性质：堆是一棵完全二叉树，除了最底层外，其他层都是满的，且最底层从左到右填充。

堆排序的基本思想是先构建一个最小堆，然后将堆顶元素（最小值）与堆中的末尾元素交换，然后将剩余元素重新调整为最小堆，重复这个过程直到所有元素都有序。

堆排序的具体步骤如下：

构建最小堆：从数组的中间位置开始，从右到左对每个非叶子节点进行调整，使其满足最小堆性质。这一步将整个数组调整为一个最小堆。

堆排序：从数组的末尾开始，依次将堆顶元素与当前末尾元素交换，然后调整剩余元素为最小堆。每次交换后，将堆的大小减1，排除已排序的元素。重复这个过程，直到堆中只剩下一个元素。

排序完成：经过堆排序后，数组中的元素按照从小到大的顺序排列。

堆排序的时间复杂度为 O(nlogn)，其中 n 是数组的长度。它是一种原地排序算法，不需要额外的空间，但由于涉及到交换操作，所以是一种不稳定的排序算法。

堆排序在实际应用中具有一定的局限性，因为它对数据的随机访问较多，对于较大规模的数据或者外部存储的数据，堆排序可能会导致较差的缓存性能。但在某些特定场景下，堆排序的性能相对较好，例如需要找出前 k 个最大或最小的元素时，堆排序可以通过部分排序来实现高效的解决方案。

最小堆也是使用数组来实现的，与最大堆类似。不同之处在于，最小堆中父节点的值小于等于其子节点的值，而最大堆中父节点的值大于等于其子节点的值。最小堆的构建和调整过程与最大堆类似，只是在比较和交换的时候使用相反的逻辑。

最小堆是使用树结构？

最小堆是一种基于数组实现的完全二叉树，而不是树结构。尽管最大堆的表示形式在视觉上看起来像是一棵树，但实际上它是通过数组来实现的。

最小堆的性质是父节点的值小于等于其子节点的值。通过使用数组来表示最小堆，可以方便地满足这一性质，并且具有一些优势：

数组是一种连续存储的数据结构，相比树结构，它具有更好的缓存性能。在访问数组元素时，可以利用 CPU 缓存的特性，提高访问效率。

数组可以通过索引直接访问元素，而不需要像树结构一样需要遍历搜索。这使得对最大堆的插入、删除等操作更加高效。

数组实现的最大堆相对于树结构来说，占用的内存空间更小。树结构需要额外的指针和连接操作，而数组只需要连续的内存空间即可。

综上所述，使用数组来实现最小堆既能满足最小堆的性质，又能提供更好的性能和节省内存空间。因此，最小堆通常采用数组来表示，而不是树结构。

我们来一行行看代码，我最喜欢debug式看代码。

首先，记住这张图，关键点在于根节点（num[0]），节点位置（num[7]之前），和叶子节点位置（num[7]之后）。

节点位置与叶子节点位置，他们之间是可以通过计算得出来的

• 所有节点位置计算：nums.length/2-1 例：13/2-1 = 5; num[5]之前的节点位置
• 节点位置与叶子节点位置计算：拿num[1]和num[5]举例
• 左节点计算：int left =2 * index + 1 例：num[1]左节点 2 * 1+1= 3 num[5]子节点 2 * 5+1= 11
• 右节点计算：int right =2 * index + 2 例：num[1]右节点 2 * 1+2= 4 num[5]子节点 2 * 5+2= 12

// 仅是我的思路代码，leetcode上大神更厉害
class MinHeap {
    public static void heapSort(int[] nums) {
    int n = nums.length;
    // 构建最小堆
    buildMinHeap(nums);
    // 进行堆排序
    for (int i = n - 1; i >= 0; i--) {
        // 将堆顶元素（最小值）与当前末尾元素交换
        swap(nums, 0, i);
        // 调整堆，保持最小堆性质
        minHeapify(nums, i, 0);
      }
  }
    public static void buildMinHeap(int[] nums) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            minHeapify(nums, n, i);
        }
    }
    public static void minHeapify(int[] nums, int heapSize, int index) {
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        if (left < heapSize && nums[left] < nums[smallest]) {
            smallest = left;
        }
        if (right < heapSize && nums[right] < nums[smallest]) {
            smallest = right;
        }
        if (smallest != index) {
            swap(nums, index, smallest);
            minHeapify(nums, heapSize, smallest);
        }
    }
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

思路：

首先，使用HashMap统计每个单词的出现频率，其中单词作为键，频率作为值。

然后，我们使用最小堆（PriorityQueue）来保存频率前k高的单词。在最小堆中，我们定义了一个自定义的比较器Lambda表达式来进行排序。比较器的逻辑如下：

首先，我们比较两个单词的频率是否相等。

如果频率相等，则按照字典序降序排列，即b.compareTo(a)。

如果频率不相等，则按照频率升序排列，即frequencyMap.get(a) -frequencyMap.get(b)。

接下来，我们遍历频率Map，将单词依次加入最小堆中。如果堆的大小超过了k，则移除堆顶的元素，保持堆的大小为k。

在调用minHeap.poll()方法时，会调用比较器（Comparator）来进行元素的比较。在这段代码中，我们使用的比较器是通过Lambda表达式定义的，它会根据单词的频率和字典序进行比较。

最后，我们将堆中的单词依次弹出，并将其添加到结果列表中。由于最小堆中的单词是按照频率升序排列的，因此我们需要将结果列表进行反转，使其按照频率降序排列。

最终，返回结果列表即为出现频率前k高的单词。

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // 统计每个单词的出现频率
        Map<String, Integer> frequencyMap = new HashMap<>();
        for (String word : words) {
            frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);
        }
        // 使用最小堆来保存频率前k高的单词
        PriorityQueue<String> minHeap = new PriorityQueue<>(
                (a, b) -> frequencyMap.get(a).equals(frequencyMap.get(b))
                        ? b.compareTo(a) : frequencyMap.get(a) - frequencyMap.get(b));
        // 遍历频率Map，维护最小堆的大小为k
        for (String word : frequencyMap.keySet()) {
            minHeap.offer(word);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        // 构建结果列表
        List<String> result = new ArrayList<>();
        while (!minHeap.isEmpty()) {
            result.add(minHeap.poll());
        }
        Collections.reverse(result);
        return result;
    }
}

时间复杂度：O(nlogk)

• n是单词的总数，k是要求的频率前k高的单词数。我们需要遍历整个单词数组来统计频率，同时最小堆的插入和弹出操作的时间复杂度为O(logk)

空间复杂度：O(n)

• 用于存储频率Map和最小堆