堆是一種特殊的樹(shù)形結(jié)構(gòu)， 堆中的數(shù)據(jù)存儲(chǔ)滿足一定的堆序。堆排序是一種選擇排序， 其算法復(fù)雜度， 時(shí)間復(fù)雜度相對(duì)于其他的排序算法都有很大的優(yōu)勢(shì)。

堆分為大頭堆和小頭堆， 正如其名， 大頭堆的第一個(gè)元素是最大的， 每個(gè)有子結(jié)點(diǎn)的父結(jié)點(diǎn)， 其數(shù)據(jù)值都比其子結(jié)點(diǎn)的值要大。小頭堆則相反。

我大概講解下建一個(gè)樹(shù)形堆的算法過(guò)程:

找到N/2 位置的數(shù)組數(shù)據(jù)， 從這個(gè)位置開(kāi)始， 找到該節(jié)點(diǎn)的左子結(jié)點(diǎn)的索引， 先比較這個(gè)結(jié)點(diǎn)的下的子結(jié)點(diǎn)， 找到最大的那個(gè)， 將最大的子結(jié)點(diǎn)的索引賦值給左子結(jié)點(diǎn)， 然后將最大的子結(jié)點(diǎn)和父結(jié)點(diǎn)進(jìn)行對(duì)比， 如果比父結(jié)點(diǎn)大， 與父節(jié)點(diǎn)交換數(shù)據(jù)。當(dāng)然， 我只是大概說(shuō)了下實(shí)現(xiàn)， 在此過(guò)程中， 還需要考慮結(jié)點(diǎn)不存在的情況。

看下代碼：

# 構(gòu)建二叉堆 def binaryHeap(arr, lenth, m):  temp = arr[m] # 當(dāng)前結(jié)點(diǎn)的值  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("二叉堆的物理順序?yàn)?")  print(arr) # 輸出二叉堆的物理順序   if __name__ == '__main__':  arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]   heapsort(arr, len(arr))

堆排序過(guò)程就是依次將最后的結(jié)點(diǎn)與首個(gè)節(jié)點(diǎn)進(jìn)行對(duì)比交換：

# 構(gòu)建二叉堆def binaryHeap(arr, lenth, m):  temp = arr[m] # 當(dāng)前結(jié)點(diǎn)的值  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] = tempdef heapsort(arr, length):  i = int(len(arr)/2)  while(i >= 0):    binaryHeap(arr, len(arr), i)    i = i - 1  print("二叉堆的物理順序?yàn)?")  print(arr) # 輸出二叉堆的物理順序  i = length-1  while(i > 0):    arr[i], arr[0] = arr[0], arr[i] # 變量交換    binaryHeap(arr, i, 0)    i = i - 1560def pop(arr):  first = arr.pop(0)  return firstif __name__ == '__main__':  arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]  heapsort(arr, len(arr))  print("堆排序后的物理順序")  print(arr) # 輸出經(jīng)過(guò)堆排序之后的物理順序  data = pop(arr)  print(data)  print(arr)

python封裝了一個(gè)堆模塊, 我們使用該模塊可以很高效的實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列

import heapqclass 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)) # 存入一個(gè)三元組    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())