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官网

秒客网

python下实现二叉堆以及堆排序

相关文章