本文共 2741 字，大约阅读时间需要 9 分钟。
这里记录下堆的相关操作。
op 1：
''' @ data: the heap array @ p : index of parent item @ n : number of data @@ Swap p and it's son items, make p the largest of them'''def swapForMaxHeap(data, n, p): ls = p << 1 | 1 rs = ls + 1 # p has two sons or just left if ls < n or rs < n: if rs < n: if data[ls] < data[rs]: ls = rs if data[p] < data[ls]: data[p], data[ls] = data[ls], data[p] return ls return -1上面函数的功能，是将p所代表的父节点与其子节点的值进行比较，与节点值大的子节点交换节点值，使得父节点的值最大，并返回与其进行交换的子节点的索引。若无交换，则返回 -1.
op 2：
''' @ data: the heap array @ p : index of parent item @ n : number of data @@ Swap p and it's son items, make p the smallest of them'''def swapForMinHeap(data, n, p): ls = p << 1 | 1 rs = ls + 1 # p has two sons or just left if ls < n or rs < n: if rs < n: if data[ls] > data[rs]: ls = rs if data[p] > data[ls]: data[p], data[ls] = data[ls], data[p] return ls return -1与上面的函数类似，只是取小的结点值。
op 3：
def Swap(data, n, p, ls = 0): fun = {} fun[0] = swapForMaxHeap fun[1] = swapForMinHeap return fun[ls](data, n, p) 将上面的两个函数进行下封装，参数ls表示的是堆的类型， 0 表示大根堆， 1 表示是小根堆。 op 4：
''' @ data : the heap array @ i : the start index to be fixUp @ n : the number of data @ ls : if 0, it is a max heap, otherwise, min one @@ '''def fixUp(data, i, n, ls = 0): if n <= 1: return if i <= 0 or i >= n: return p = (i - 1) >> 1 while p >= 0: Swap(data, n, p, ls) p = (p - 1) >> 1结点的上溯过程，用于插入操作，插入的时候，先将新结点的值插入到堆数组的尾部，因为这个新的结点可能违反堆的性质，需要向上调整，直到调整到最顶端。
op 5：
def fixDown( data, i, n, ls = 0): if n <= 1: return if i < 0 or i >= n: return while i <= n - 1: index = Swap(data, n, i, ls) if index == -1: break i = index结点的下沉过程，用于删除和堆的建立。删除的操作，只在堆顶进行，即删除堆顶元素，删除时，将堆的最后元素与堆顶进行交换，交换后，新的堆顶元素可能违反堆的性质，所以需要向下调整。
op 6：
''' @ data: data array that adjust to be heap @ n : number of data @ ls : 0-max heap, 1- min heap'''def buildHeap(data, n, ls = 0): if n <= 1: return for i in xrange( (n >> 1) - 1, -1, -1): fixDown(data, i, n, ls)堆的建立其实不需要从0开始，也就是将数组中的元素一个个的插入到空的堆中，因为若没有大小堆的大小限制，给定的数组也可以视为是一种堆，只不过是杂乱无章的堆，我们只需要对这些元素进行下调整就可以了，就是从最后一个非叶子结点开始，向下调整。
op 7：
def insert(data, new_x, ls = 0): data.append(new_x) n = len( data ) fixUp(data, n - 1, n , ls)这就是插入操作了，插入的时候将新元素插入到最后，然后上溯，调整为符合堆的性质。
op 8：
def delete(data, n, ls = 0): if n <= 0: return if n == 1: del data[0] return data[0], data[-1] = data[-1], data[0] del data[-1] print data fixDown(data, 0, n - 1, ls)删除操作允许在堆顶进行，删除后那个空缺这么办呢?身份最单调的就是最后一个结点，因为其肯定不会有孩子结点，而且也不会打乱下标，所以我们用其与堆顶交换，代码里是为了说明交换的意思，其实只要将最后结点的值赋值给堆顶就好了，即 data[ 0 ] = data[ -1]。然后删除最后一个结点。从上向下调整。
op 9：
def heapSort(data, n, ls = 0): if n <= 1: return for i in xrange(n - 1, -1, -1): data[i], data[0] = data[0], data[i] fixDown(data, 0, i, ls) data.reverse() print data这就是堆排序的排序了，以小根堆为例，堆顶就是整个序列的最小，将其与最后的结点交换，然后调整，调整后的堆顶又是相对最小的，再交换。
转载地址：http://cumji.baihongyu.com/