簡介
堆是一種完全二叉樹抡柿，有最大堆和最小堆兩種蒋得。
-
最大堆: 每個(gè)節(jié)點(diǎn)户辱，都比葉子節(jié)點(diǎn)大穷蛹，如：
最小堆：和最大堆相反
堆的特性
堆是一種完全二叉樹铭污，具備二叉樹的特性：
- 父節(jié)點(diǎn)下標(biāo)：
parent = int((i-1) / 2)# 取整 - 左節(jié)點(diǎn)下標(biāo)：
left = 2 * i + 1 - 右節(jié)點(diǎn)下標(biāo)：
right = 2 * i + 2
如：節(jié)點(diǎn)60的父節(jié)點(diǎn)下標(biāo)是1迫吐，本身節(jié)點(diǎn)下標(biāo)是3宰缤，左下標(biāo)7痊剖，右下標(biāo)8
堆的表示
堆可以用數(shù)組表示告丢，如
[10,7,2,5,1]
堆的python實(shí)現(xiàn)
class Array(object):
def __init__(self, size=32):
self._size = size
self._items = [None] * size
def __getitem__(self, index):
return self._items[index]
def __setitem__(self, index, value):
self._items[index] = value
def __len__(self):
return self._size
def clear(self, value=None):
for i in range(len(self._items)):
self._items[i] = value
def __iter__(self):
for item in self._items:
yield item
class MaxHeap(object):
def __init__(self, maxsize=None):
self.maxsize = maxsize
self._elements = Array(maxsize)
self._count = 0
def __len__(self):
return self._count
def add(self, value):
if self._count >= self.maxsize:
raise Exception('full')
self._elements[self._count] = value
self._count += 1
self._siftup(self._count-1) # 維持堆的特性
def _siftup(self, ndx):
if ndx > 0:
parent = int((ndx-1)/2)
if self._elements[ndx] > self._elements[parent]: # 如果插入的值大于 parent枪蘑，一直交換
self._elements[ndx], self._elements[parent] = self._elements[parent], self._elements[ndx]
self._siftup(parent) # 遞歸
def extract(self):
if self._count <= 0:
raise Exception('empty')
value = self._elements[0] # 保存 root 值
self._count -= 1
self._elements[0] = self._elements[self._count] # 最右下的節(jié)點(diǎn)放到root后siftDown
self._siftdown(0) # 維持堆特性
return value
def _siftdown(self, ndx):
left = 2 * ndx + 1
right = 2 * ndx + 2
# determine which node contains the larger value
largest = ndx
if (left < self._count and # 有左孩子
self._elements[left] >= self._elements[largest] and
self._elements[left] >= self._elements[right]): # 原書這個(gè)地方?jīng)]寫實(shí)際上找的未必是largest
largest = left
elif right < self._count and self._elements[right] >= self._elements[largest]:
largest = right
if largest != ndx:
self._elements[ndx], self._elements[largest] = self._elements[largest], self._elements[ndx]
self._siftdown(largest)
def test_maxheap():
import random
n = 5
h = MaxHeap(n)
for i in range(n):
h.add(i)
for i in reversed(range(n)):
assert i == h.extract()
def heapsort_reverse(array):
length = len(array)
maxheap = MaxHeap(length)
for i in array:
maxheap.add(i)
res = []
for i in range(length):
res.append(maxheap.extract())
return res
def test_heapsort_reverse():
import random
l = list(range(10))
random.shuffle(l)
assert heapsort_reverse(l) == sorted(l, reverse=True)
def heapsort_use_heapq(iterable):
from heapq import heappush, heappop
items = []
for value in iterable:
heappush(items, value)
return [heappop(items) for i in range(len(items))]
def test_heapsort_use_heapq():
import random
l = list(range(10))
random.shuffle(l)
assert heapsort_use_heapq(l) == sorted(l)
- Array 實(shí)現(xiàn)一個(gè)數(shù)組，用于填充堆數(shù)據(jù)
- 實(shí)現(xiàn)一個(gè)最大堆MaxHeap
- add方法用于增加堆節(jié)點(diǎn)時(shí)岖免，每次增加后會(huì)調(diào)用_siftup進(jìn)行調(diào)整岳颇。
- _siftup傳入增加節(jié)點(diǎn)的最后一個(gè)下標(biāo)作為參數(shù)，這個(gè)節(jié)點(diǎn)的值與父節(jié)點(diǎn)對比颅湘，根據(jù)堆性質(zhì)看是否需要交換话侧。
- extract提取最大值，并_siftdown進(jìn)行重整闯参，維持堆特性瞻鹏。
- _siftdown進(jìn)行比較，交換鹿寨，遞歸之新博。
python heapd模塊
python自帶的內(nèi)置heapd模塊，用于實(shí)現(xiàn)堆的相關(guān)操作脚草。
