(二叉)堆数据结构是一种数组对象。可以被视为一棵完全二叉树。数中每个节点与数组中存放该节点值的那个元素对应。树的每一层都是填满的。最后一层可能除外(最后一层从一个节点的左子树开始填) -引用自《算法导论》
再抄一遍复习一下
从无序的数组构建一个完整的堆,最好及最坏的情况下,建立堆时间复杂度均为o(nlgn) (建堆o(n),调堆o(lgn),整体耗时 o(nlog2n))。算法排序不稳定。
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) 2)each adjust, time complexity 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 3)each adjust, time complexity o(lgn) ''' 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()