Python实现标准堆与索引堆的完整代码解析
本文详细讲解如何使用Python实现标准堆和索引堆。首先介绍基于数组的标准大根堆构建、上浮下沉调整及优先队列操作。随后深入索引堆，通过维护索引数组解决动态数据更新问题，并引入to_index数组优化查找效率，提供完整的Python代码示例与逻辑分析。
堆本质上是一棵完全二叉树。根据节点大小关系，堆可分为大根堆和小根堆：大根堆要求父节点的值大于或等于其左右子节点的值，且左右子树同样满足这一性质；小根堆则相反，父节点值小于或等于子节点值。基于堆的特性，可以高效地实现优先队列。
由于堆是完全二叉树，可以使用数组进行存储，索引范围从0到length-1。对于索引为i的节点，其左子节点索引为2i+1，右子节点索引为2i+2。长度为length的堆中，最后一个非叶子节点的索引为length//2-1（//表示向下取整）。任意节点i的父节点索引为(i-1)//2。
以大根堆为例，每次插入或删除元素后，为保持堆的结构性质，需进行调整。调整方向主要有两种：一是从上往下，将较小的值逐步下沉；二是从下往上，将较大的值逐步上浮。
具体实现代码如下：
首先定义几个基础魔术方法：构造函数接收可选的data列表并初始化；__len__方法返回data数组的长度；__str__方法用于打印data内容。
def __init__(self, data=[]):
self.data = data
self.construct_heap()
def __len__(self):
return len(self.data)
def __str__(self):
return str(self.data)
定义swap函数，用于便捷地交换数组中指定两个索引位置的元素值。
def swap(self, i, j):
self.data[i], self.data[j] = self.data[j], self.data[i]
定义float_up方法，实现大元素上浮逻辑。当当前节点不是根节点，且当前节点值大于父节点值时，执行交换并继续向上比较。
def float_up(self, i):
while i > 0 and self.data[i] > self.data[(i - 1) // 2]:
self.swap(i, (i - 1) // 2)
i = (i - 1) // 2
定义sink_down方法，实现小元素下沉逻辑。当当前节点不是叶子节点时，比较其与左右子节点的值，若当前值小于子节点中较大的那个，则与较大子节点交换位置，并继续下沉。
def sink_down(self, i):
while i < len(self) // 2:
l, r = 2 * i + 1, 2 * i + 2
if r < len(self) and self.data[l] < self.data[r]:
l = r
if self.data[i] < self.data[l]:
self.swap(i, l)
i = l
实现append方法，支持动态添加数据。将新数据追加到数组末尾，随后调用float_up方法将其上浮至正确位置。
def append(self, data):
self.data.append(data)
self.float_up(len(self) - 1)
实现pop_left方法，用于获取并移除堆顶最大元素（即优先队列首元素）。操作包括：交换首尾元素，移除原末尾元素，随后对新的首元素调用sink_down方法使其下沉至合适位置。
def pop_left(self):
self.swap(0, len(self) - 1)
r = self.data.pop()
self.sink_down(0)
return r
若需在初始化时传入数据列表，需一次性构建整个堆，而非逐个插入。实现方式是从最后一个非叶子节点开始，逆序对每个节点执行sink_down操作即可完成建堆。
def construct_heap(self):
for i in range(len(self) // 2 - 1, -1, -1):
self.sink_down(i)
至此，基本堆的代码编写完成。
然而，若需动态修改堆中数据，标准堆无法满足需求，因为索引会随堆结构调整而改变，无法稳定标识特定数据。为此，需要引入索引堆（Index Heap）。
在索引堆中，堆数组不直接存储数据，而是存储数据的索引。
假设输入数据数组arr为[45, 20, 12, 5, 35]。在索引堆调整过程中，实际调整的是索引数组，真实数据数组arr保持不变，因此arr[0]始终指向45，arr[1]始终指向20。
因此代码需调整：在构造函数中增加一个索引数组index_arr，其下标从0开始，与数据数组下标一一对应。
def __init__(self, data=[]):
self.data = data
self.index_arr = list(range(len(self.data)))
self.construct_heap()
同时修改返回堆长度的魔术方法__len__，使其返回index_arr的长度。
def __len__(self):
return len(self.index_arr)
调整swap方法，使其交换index_arr中的索引值，而非直接交换数据。
def swap(self, i, j):
self.index_arr[i], self.index_arr[j] = self.index_arr[j], self.index_arr[i]
相应调整float_up和sink_down方法中的比较逻辑，使其通过index_arr间接访问数据值进行比较。
def float_up(self, i):
while i > 0 and self.data[self.index_arr[i]] > self.data[self.index_arr[(i - 1) // 2]]:
self.swap(i, (i - 1) // 2)
i = (i - 1) // 2
def sink_down(self, i):
while i < len(self) // 2:
l, r = 2 * i + 1, 2 * i + 2
if r < len(self) and self.data[self.index_arr[l]] < self.data[self.index_arr[r]]:
l = r
if self.data[self.index_arr[i]] < self.data[self.index_arr[l]]:
self.swap(i, l)
i = l
在append数据时，需同步更新index_arr，将新数据的索引追加到index_arr末尾。
def append(self, data):
self.data.append(data)
self.index_arr.append(len(self))
self.float_up(len(self) - 1)
在移除数据时，如前所述，数据数组data_arr按append顺序存储，操作仅调整index_arr的顺序。
例如，若data_arr为[42, 30, 74, 60]，则相应的index_arr应为[2, 3, 0, 1]，分别指向74, 60, 42, 30。
当执行popleft移除最大元素时，data_arr中的74被移除后变为[42, 30, 60]。此时原最大索引由3变为2，若index_arr中仍保留索引3，访问data_arr[3]将导致索引溢出。由于74的原索引为2，需将index_arr中所有大于原移除索引（即大于2）的索引值减1，以修正索引偏移。
综上所述，删除元素时，标准堆是交换data_arr首尾后删除尾部再下沉。索引堆则先交换index_arr首尾，删除index_arr尾部元素，此时data_arr未动，index_arr与data_arr仍一一对应。执行sink_down后，再删除data_arr中对应索引的元素，最后将index_arr中所有大于原移除索引的值减1。
def pop_left(self):
self.swap(0, len(self) - 1)
r = self.index_arr.pop()
self.sink_down(0)
self.data.pop(r)
for i, index in enumerate(self.index_arr):
if index > r:
self.index_arr[i] -= 1
return r
索引堆增加了更新操作，支持动态修改数据。更新时，先直接修改data_arr中指定索引的数据，然后在index_arr中遍历查找该数据对应的索引位置（耗时O(N)）。找到位置后，由于无法确定新值与相邻元素的大小关系，需先执行float_up再执行sink_down。
def update(self, i, data):
self.data[i] = data
for index_index, index in enumerate(self.index_arr):
if index == i:
target = index_index
self.float_up(target)
self.sink_down(target)
可以看出，索引堆在插入时较快，但删除和更新时需遍历查找索引，效率较低。为加速查找index_arr中特定数据对应的索引，可引入第三个数组to_index，用于建立数据值到索引位置的映射。
例如，对于数据数组[75, 54, 65, 90]。
此时index_arr为[3, 0, 2, 1]。若要更新data[3]（即90），需遍历index_arr找到值为3的位置，该位置索引为0。为此建立to_index数组，使to_index[3]的值为0，即直接通过to_index获取数据在index_arr中的位置。
修改后，index_arr存放的元素分别为[1, 3, 2, 0]。
调整swap方法，在交换index_arr元素的同时，同步交换to_index中对应索引的值，以维护to_index的正确性。
def swap(self, i, j):
self.index_arr[i], self.index_arr[j] = self.index_arr[j], self.index_arr[i]
self.to_index[self.index_arr[i]], self.to_index[self.index_arr[j]] = self.to_index[self.index_arr[j]], \
self.to_index[self.index_arr[i]]
在update方法中，当更新位置i的元素时，无需遍历查找，直接通过to_index[i]即可获取该数据在index_arr中的索引位置，从而进行float_up和sink_down操作。
def update(self, i, data):
self.data[i] = data
target = self.to_index[i]
self.float_up(target)
self.sink_down(target)
最后修改pop_left方法，此时需维护data_arr、index_arr和to_index三个数组。
具体步骤为：交换index_arr首尾元素，弹出尾部索引存入r；对新的头部元素执行sink_down；从data_arr中移除索引为r的元素；从to_index中移除索引为r的元素；最后将index_arr中所有大于原索引r的值减1，以修正索引偏移。
def pop_left(self):
self.swap(0, len(self) - 1)
r = self.index_arr.pop()
self.sink_down(0)
self.data.pop(r)
self.to_index.pop(r)
for i in range(r, len(self)):
self.index_arr[self.to_index[i]] -= 1
return r
以上即为Python实现标准堆与索引堆的完整方法及代码示例，希望对学习有所帮助，欢迎支持本站。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
