python下實現二叉堆以及堆排序

python下實現二叉堆以及堆排序

堆是一種特殊的樹形結構, 堆中的數據存儲滿足一定的堆序。堆排序是一種選擇排序, 其演算法複雜度, 時間複雜度相對於其他的排序演算法都有很大的優勢。

堆分為大頭堆和小頭堆, 正如其名, 大頭堆的第一個元素是最大的, 每個有子結點的父結點, 其數據值都比其子結點的值要大。小頭堆則相反。

我大概講解下建一個樹形堆的演算法過程:
找到N/2 位置的數組數據, 從這個位置開始, 找到該節點的左子結點的索引, 先比較這個結點的下的子結點, 找到最大的那個, 將最大的子結點的索引賦值給左子結點, 然後將最大的子結點和父結點進行對比, 如果比父結點大, 與父節點交換數據。當然, 我只是大概說了下實現, 在此過程中, 還需要考慮結點不存在的情況。看下代碼:

# 構建二叉堆 
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())

具體請看heapq官網