Python下实现二叉堆以及堆排序-演道网

# 构建二叉堆
def binaryHeap(arr, lenth, m):
temp = arr[m] # 当前结点的值
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp

def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1

print("二叉堆的物理顺序为:")
print(arr) # 输出二叉堆的物理顺序

if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]

heapsort(arr, len(arr))

# 构建二叉堆
def binaryHeap(arr, lenth, m):
temp = arr[m]  # 当前结点的值
while(2*m+1 < lenth):
lchild = 2*m+1
if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:
lchild = lchild + 1
if temp < arr[lchild]:
arr[m] = arr[lchild]
else:
break
m = lchild
arr[m] = temp

def heapsort(arr, length):
i = int(len(arr)/2)
while(i >= 0):
binaryHeap(arr, len(arr), i)
i = i - 1

print("二叉堆的物理顺序为:")
print(arr)  # 输出二叉堆的物理顺序

i = length-1
while(i > 0):
arr[i], arr[0] = arr[0], arr[i]  # 变量交换
binaryHeap(arr, i, 0)
i = i - 1560

def pop(arr):
first = arr.pop(0)
return first

if __name__ == '__main__':
arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]

heapsort(arr, len(arr))

print("堆排序后的物理顺序")
print(arr)  # 输出经过堆排序之后的物理顺序

data = pop(arr)
print(data)

print(arr)

python封装了一个堆模块, 我们使用该模块可以很高效的实现一个优先队列:

import heapq

class Item:
def __init__(self, name):
self.name = name

def __repr__(self):
return 'Item({!r})'.format(self.name)

class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0

def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))  # 存入一个三元组
self._index += 1

def pop(self):
return heapq.heappop(self._queue)[-1]  # 逆序输出

if __name__ == '__main__':
p = PriorityQueue()
p.push(Item('foo'), 1)
p.push(Item('bar'), 5)
p.push(Item('spam'), 4)
p.push(Item('grok'), 1)

print(p.pop())
print(p.pop())