快捷導(dǎo)航

python下實(shí)現(xiàn)二叉堆以及堆排序的示例

更新時(shí)間：2017年09月29日 08:30:53 作者：又見阿郎

下面小編就為大家?guī)硪黄猵ython下實(shí)現(xiàn)二叉堆以及堆排序的示例。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

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

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

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

找到N/2 位置的數(shù)組數(shù)據(jù)，從這個(gè)位置開始，找到該節(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)行對比，如果比父結(jié)點(diǎn)大，與父節(jié)點(diǎn)交換數(shù)據(jù)。當(dāng)然，我只是大概說了下實(shí)現(xiàn)，在此過程中，還需要考慮結(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))

堆排序過程就是依次將最后的結(jié)點(diǎn)與首個(gè)節(jié)點(diǎn)進(jì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) # 輸出二叉堆的物理順序

  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) # 輸出經(jīng)過堆排序之后的物理順序

  data = pop(arr)
  print(data)

  print(arr)

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

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)) # 存入一個(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())

具體請看heapq官網(wǎng)

以上這篇python下實(shí)現(xiàn)二叉堆以及堆排序的示例就是小編分享給大家的全部內(nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: