[人工智能]python实现最大堆与堆排序

class MaxHeap:
    heap = []
    @staticmethod
    def insertNum(num):
        """ 插入元素 """
        MaxHeap.heap.append(num)
        MaxHeap.shift_up()

    @staticmethod
    def shift_up():
        """ 第一个元素放在索引为0的位置上 """
        current_id = len(MaxHeap.heap)-1
        parent_id = (current_id-1)//2
        while current_id > 0:
            if MaxHeap.heap[parent_id] >= MaxHeap.heap[current_id]:
                break
            else:
                MaxHeap.heap[parent_id], MaxHeap.heap[current_id] = \
                MaxHeap.heap[current_id],MaxHeap.heap[parent_id]
                current_id = parent_id
                parent_id = (current_id-1) // 2

    @staticmethod
    def deleteNum(num):
        """ 删除元素 """
        if num == MaxHeap.heap[-1]:
            MaxHeap.heap.pop()
            return
        temp = MaxHeap.heap.pop() # 最后一个元素
        ind = MaxHeap.heap.index(num)
        MaxHeap.heap[ind] = temp
        MaxHeap.shift_down(ind)

    @staticmethod
    def shift_down(ind):
        current_id = ind
        child_id_left = current_id*2 + 1
        child_id_right = current_id*2 + 2
        while current_id < len(MaxHeap.heap) - 1:
            if current_id*2 + 1 > len(MaxHeap.heap) - 1:
                # 当前节点为叶子节点, shift_down完成
                break
            if current_id*2 + 1 == len(MaxHeap.heap) - 1:
                # 只有左孩子
                if MaxHeap.heap[current_id] > MaxHeap.heap[-1]:
                    break
                else:
                    MaxHeap.heap[current_id],MaxHeap.heap[-1] = MaxHeap.heap[-1], \
                    MaxHeap.heap[current_id]
                    break
            # 既有左孩子，又有右孩子
            if MaxHeap.heap[current_id] > max(MaxHeap.heap[child_id_left],
                                            MaxHeap.heap[child_id_right]):
                # 如果已经比左右孩子大
                break
            else:
                # 和那个最大的孩子节点交换
                childInx = child_id_left if MaxHeap.heap[child_id_left] > MaxHeap.heap[child_id_right] \
                    else child_id_right
                MaxHeap.heap[childInx],MaxHeap.heap[current_id] = \
                MaxHeap.heap[current_id],MaxHeap.heap[childInx]
                current_id = childInx
                child_id_left = current_id*2+1
                child_id_right = current_id*2 + 2

    @staticmethod
    def extract_max():
        num = MaxHeap.heap[0]
        try:
            MaxHeap.deleteNum(num)
            return num
        except:
            return num

    @staticmethod
    def heap_sort(arr):
        for item in arr:
            MaxHeap.insertNum(item) # 建堆

        # 将堆顶元素一个一个弹出置入arr
        for i in range(len(arr)):
            arr[i] = MaxHeap.extract_max()

    @staticmethod
    def heapify(arr):
        MaxHeap.heap = arr
        n = (len(arr)-1)//2
        while n>=0:
            MaxHeap.shift_down(n)
            n -=1

    @staticmethod
    def heap_sort2(arr):
        MaxHeap.heapify(arr)
        res = []
        for i in range(len(arr)):
            res.append(MaxHeap.extract_max())
        return res

if __name__ == '__main__':
    s = MaxHeap()
    arr = [2,1,4,3,5]
    s.heap_sort(arr)
    print('sort1: ',arr)
    arr2 = [2, 1, 4, 3, 5]
    ans = s.heap_sort2(arr2)
    print('sort2: ', ans)