Python堆排序（最大堆），python堆排序最大堆,# -*- coding

Python堆排序（最大堆），python堆排序最大堆,# -*- coding

# -*- coding: utf-8 -*-# import mathdef parent(i):    """父结点下标"""    return int((i - 1) >> 1); # floor((i-1)/2)def left(i):    """左儿子下标"""    return (i << 1) + 1; # 2i + 1def right(i):    """右儿子下标"""    return (i << 1) + 2; # 2i + 2def max_heapify(A, i, heap_size):    """ 最大堆化A[i]为根的子树，伪码如下：    MAX-HEAPIFY(A, i)    1  l ← LEFT(i)    2  r ← RIGHT(i)    3  if l <= heap-size[A] and A[l] > A[i] // A[i]，A[LEFT[A]]中找出最大的    4    then largest ← l    5    else largest ← i    6  if r <= heap-size[A] and A[r] > A[largest] // A[i]，A[LEFT[A]]，A[RIGHT[i]]中找出最大的    7    then largest ← r    8  if largest != i // A[i]为最大时结束，否则继续递归    9    then exchange A[i] &#8596; A[largest] // 交换A[i]，A[largest]，使得满足最大堆性质    10        MAX-HEAPIFY(A, largest) // 递归    # 注：上述下标是从1开始的，编程时都从0开始了。    T(n) = O(lgn)    Args:        A (Sequence): 序列A        i (int): 下标i        heap_size (int): 存放在A中的堆元素个数    """    l, r = left(i), right(i)    if l < heap_size and A[l] > A[i]:        largest = l    else:        largest = i    if r < heap_size and A[r] > A[largest]:        largest = r    if largest != i:        A[i], A[largest] = A[largest], A[i]        max_heapify(A, largest, heap_size)def build_max_heap(A):    """构造成最大堆，伪码如下：    BUILD-MAX-HEAP(A)    1  heap-size[A] ← length[A] // 堆元素个数为数组大小    2  for i ← floor(length[A]/2) downto 1 // 自最后个父结点向上    3    do MAX-HEAPIFY(A, i) // 最大堆化A[i]为根的子树    T(n) = O(n)    Args:        A (Sequence): 序列A    """    heap_size = len(A)    parent_last = parent(heap_size - 1) # 最后一个下标的父结点    for i in range(parent_last, -1, -1): # parent_last downto 0        max_heapify(A, i, heap_size)def heap_sort(A):    """堆排序，伪码如下：    HEAPSORT(A)    1  BUILD-MAX-HEAP(A) // 构造成最大堆    2  for i ← length[A] downto 2    3    do exchange A[1] &#8596; A[i] // 最大元素A[1]与A[n]互换    4       heap-size[A] ← heap-size[A] - 1 // 减小heap-size[A]    5       MAX-HEAPIFY(A, 1) // 保持最大堆性质    T(n) = O(nlgn)    Args:        A (Sequence): 序列A    """    build_max_heap(A)    heap_size = len(A)    for i in range(heap_size - 1, 0, -1):        A[0], A[i] = A[i], A[0]        heap_size -= 1        max_heapify(A, 0, heap_size)if __name__ == '__main__':    import random, timeit    items = range(10000)    random.shuffle(items)    def test_sorted():        print(items)        sorted_items = sorted(items)        print(sorted_items)    def test_heapq():        from heapq import heappush, heappop        def heapsort(iterable):            'Equivalent to sorted(iterable)'            h = []            for value in iterable:                heappush(h, value)            return [heappop(h) for i in range(len(h))]        print(items)        sorted_items = heapsort(items)        print(sorted_items)    def test_heap_sort():        print(items)        heap_sort(items)        print(items)    test_methods = [test_sorted, test_heapq, test_heap_sort]    for test in test_methods:        name = test.__name__ # test.func_name        t = timeit.Timer(name + '()', 'from __main__ import ' + name)        print(name + ' takes time : %f' % t.timeit(1))#该片段来自于http://byrx.net