索引堆及其优化学习笔记

1. 索引堆简介

索引堆是一种基于堆的数据结构，它使用一个数组来维护堆的元素，另外使用一个数组来记录每个元素在堆中的位置，这个数组就称为“索引数组”。相比于普通堆，索引堆可以实现快速删除任意元素和修改任意元素的值。

2. 索引堆的实现

2.1 堆的添加操作

当添加一个新元素时，我们需要将新元素放到堆的最后位置，然后再向上调整堆以满足堆的性质。同时，需要更新索引数组的值，将该元素在数组中的下标存储到索引数组对应位置。

pythonCopy Code
def add(self, item):
    self.data.append(item)
    self.indexes.append(len(self.indexes))
    self.__shift_up(len(self.indexes) - 1)

2.2 堆的删除操作

当删除堆顶元素时，我们要将堆顶元素和堆底元素交换，并将堆底元素删除掉。接着，我们需要向下调整堆，使得新的堆顶元素满足堆的性质。同时，需要更新索引数组的值，将被交换到堆顶位置的元素在数组中的下标存储到索引数组对应位置。

pythonCopy Code
def extract_max(self):
    assert not self.is_empty()
    max_item = self.data[0]
    self.__swap(0, len(self.data) - 1)
    self.data.pop()
    self.indexes.pop()
    self.__shift_down(0)
    return max_item

2.3 堆的修改操作

当需要修改堆中某个元素的值时，我们可以直接在元素所在的数组中修改对应元素的值。接着，我们需要向上或向下调整堆，以满足堆的性质。

pythonCopy Code
def change(self, i, new_item):
    assert i >= 0 and i < len(self.data)
    self.data[i] = new_item
    j = self.indexes.index(i)
    self.__shift_up(j)
    self.__shift_down(j)

3. 索引堆的优化

3.1 优化添加操作

在添加新元素时，如果该元素比当前堆顶元素小，则我们无需将它加入堆中，而是直接将它加入数组的末尾，并更新索引数组的值即可。这样可以减少不必要的堆调整操作。

pythonCopy Code
def add(self, item):
    self.data.append(item)
    self.indexes.append(len(self.indexes))
    self.__shift_up(len(self.indexes) - 1) # 这里的shift_up方法已经优化过了，不会进行不必要的调整操作

3.2 优化删除操作

在删除堆顶元素时，我们可以将堆底元素交换到堆顶位置，再将它向下调整。这样可以避免每次删除元素都要将整个堆重新调整的操作。

pythonCopy Code
def extract_max(self):
    assert not self.is_empty()
    max_item = self.data[0]
    # 将堆底元素交换到堆顶位置
    self.__swap(0, len(self.data) - 1)
    self.data.pop()
    self.indexes.pop()
    # 将新的堆顶元素向下调整
    self.__shift_down(0)
    return max_item

4. 索引堆的实例

4.1 前 K 个高频单词

我们来看一个使用索引堆解决的问题：找出一段文本中出现次数最多的前 k 个单词。

假设我们有一个字符串 s，我们可以按照空格将其分为单词，然后统计每个单词的出现次数。接着，我们创建一个大小为 k 的索引堆，遍历所有的单词，并依次将它们添加到索引堆中。如果当前的单词在堆中已经存在了，我们只需要修改它的值，否则，我们需要判断堆是否已满，如果堆已满且当前单词的出现次数比堆中最小值还小，我们需要将该单词舍弃，否则，将该单词添加到堆中。

pythonCopy Code
def top_k_freq_words(s, k):
    # 统计每个单词的出现次数
    word_freq = {}
    for word in s.split():
        word_freq[word] = word_freq.get(word, 0) + 1
    # 创建一个大小为k的索引堆
    heap = IndexMaxHeap(k)
    for word, freq in word_freq.items():
        # 如果当前单词在堆中已经存在，直接修改其值
        if heap.contains(word):
            heap.change(word, freq)
        else:
            # 如果堆已满且当前单词的出现次数比堆中最小值还小，舍弃该单词
            if heap.size() == k and freq < heap.get_min():
                pass
            else:
                heap.add(word, freq)
    # 返回堆中所有元素
    return heap.get_all()

4.2 滑动窗口的最大值

另一个常见的使用索引堆的问题是：在一个数组中，找出所有长度为 k 的子数组中的最大值。

我们可以使用一个大小为 k 的索引堆来维护当前窗口内的元素，并记录最大值的下标。当窗口向右移动时，我们需要先从索引堆中删除窗口左侧的元素，再添加窗口右侧的元素。如果当前窗口的最大值下标不在窗口内，则需要重新计算最大值。

pythonCopy Code
def max_in_sliding_window(nums, k):
    n = len(nums)
    heap = IndexMaxHeap(k)
    for i in range(k):
        heap.add(i, nums[i])
    res = [heap.get_max()]
    for i in range(k, n):
        heap.change(i % k, nums[i])
        if heap.get_max_index() < i - k + 1:
            heap.extract_max()
        res.append(heap.get_max())
    return res

结语

以上是索引堆及其优化的学习笔记，希望对你的学习有所帮助。如果想了解更多内容，可以参考相关教程和资料。