代码如下:
# -*- coding: utf-8 -*-
class heap(object):
@classmethod def parent(cls, i): “””父结点下标””” return int((i – 1) >> 1);
@classmethod def left(cls, i): “””左儿子下标””” return (i a[largest]: largest = r if largest != i: a[i], a[largest] = a[largest], a[i] cls.max_heapify(a, largest, heap_size)
def maximum(self): “””返回最大元素，伪码如下： heap-maximum(s) 1 return a[1]
t(n) = o(1) “”” return self[0]
def extract_max(self): “””去除并返回最大元素，伪码如下： heap-extract-max(a) 1 if heap-size[a] < 1 2 then error "heap underflow" 3 max ← a[1] 4 a[1] ← a[heap-size[a]] // 尾元素放到第一位 5 heap-size[a] ← heap-size[a] - 1 // 减小heap-size[a] 6 max-heapify(a, 1) // 保持最大堆性质 7 return max
t(n) = θ(lgn) “”” heap_size = len(self) assert heap_size > 0, “heap underflow” val = self[0] tail = heap_size – 1 self[0] = self[tail] self.max_heapify(self, 0, tail) self.pop(tail) return val
def increase_key(self, i, key): “””将i处的值增加到key，伪码如下： heap-increase-key(a, i, key) 1 if key < a[i] 2 the error "new key is smaller than current key" 3 a[i] ← key 4 while i > 1 and a[parent(i)] < a[i] // 不是根结点且父结点更小时 5 do exchange a[i] ↔ a[parent(i)] // 交换两元素 6 i ← parent(i) // 指向父结点位置
t(n) = θ(lgn) “”” val = self[i] assert key >= val, “new key is smaller than current key” self[i] = key parent = self.parent while i > 0 and self[parent(i)] < self[i]: self[i], self[parent(i)] = self[parent(i)], self[i] i = parent(i)
def insert(self, key): “””将key插入a，伪码如下： max-heap-insert(a, key) 1 heap-size[a] ← heap-size[a] + 1 // 对元素个数增加 2 a[heap-size[a]] ← -∞ // 初始新增加元素为-∞ 3 heap-increase-key(a, heap-size[a], key) // 将新增元素增加到key
t(n) = θ(lgn) “”” self.append(float(‘-inf’)) self.increase_key(len(self) – 1, key)
if __name__ == ‘__main__’: import random
keys = range(10) random.shuffle(keys) print(keys)
queue = maxpriorityqueue() # 插入方式建最大堆 for i in keys: queue.insert(i) print(queue)
print(‘*’ * 30)
for i in range(len(keys)): val = i % 3 if val == 0: val = queue.extract_max() # 去除并返回最大元素 elif val == 1: val = queue.maximum() # 返回最大元素 else: val = queue[1] + 10 queue.increase_key(1, val) # queue[1]增加10 print(queue, val)
print([queue.extract_max() for i in range(len(queue))])