最大堆排序-python实现

【数据结构】最大堆排序-python实现

堆排序介绍

时间复杂度

从无序的数组构建一个完整的堆，最好及最坏的情况下，建立堆时间复杂度均为o(nlgn) （建堆o(n)，调堆o(lgn)，整体耗时 o(nlgn)）。算法排序不稳定。

代码实现

class MaxHeap(object):
    ''' try to build a max heap structure
    1) would store data in array, tree would be generated in logic;
    2) provide insert and adjust method;
    '''
    _array = []
    _size   = 0

    def __init__(self, heap_arr = []):
        ''' init of heap
        1) use given heap_arr, build a maxheap
        '''
        self._array = heap_arr
        print(self._array)
        self._size  = len(heap_arr)
        self.BuildHeap()

    def BuildHeap(self):
        ''' according to self._array, build heap
        1) time cost is o(n)
        '''
        # the last Non-leaf node
        lattest = int(self._size/2)

        for pos in range(lattest, -1, -1):
            self._adjust_heap(pos)

    def _adjust_heap(self, ad_pos = 0, comp_func = lambda x, y: x > y):
        ''' adjust heap, comparing function would be comp_func
        1) for node, count i, left is 2*i+1 and right is 2*i+2
        2) default choice is generate max_heap
        '''
        if ad_pos < 0 or ad_pos >= self._size:
            return False
        left     = 2 * ad_pos + 1
        right    = 2 * ad_pos + 2
        this_ned = ad_pos
        arr      = self._array

        this_ned = left if left < self._size and \
            comp_func(arr[left], arr[this_ned]) else this_ned
        this_ned = right if right < self._size and \
            comp_func(arr[right], arr[this_ned]) else this_ned

        if this_ned != ad_pos:
            print("swap %d with %d: %d - %d" % \
                (ad_pos, this_ned, arr[ad_pos], arr[this_ned]))
             print(self._array)
            arr[ad_pos], arr[this_ned] = arr[this_ned], arr[ad_pos]
            self._adjust_heap(this_ned)
        return True

    def Pop(self):
        ''' return the max and adjust heap
        '''
        if self._size <= 0:
            return
        pop_num = self._array[0]
        self._array[0] = self._array[-1]
        del(self._array[-1])
        self._size -= 1
        # only when arr size >=2, adjust heap
        if self._size >= 2:
            self._adjust_heap(0)
        return pop_num

运行示例

    heap_ar = [1, 1, 2, 3, 4, 5, 3]
    heap = MaxHeap(heap_ar)

    pop_number = heap.Pop()
    while pop_number:
        print(pop_number)
        pop_number = heap.Pop()