python堆排序

堆排序介紹

堆排序，顧名思義，就是基于堆。是以先來介紹一下堆的概念。

堆分為最大堆和最小堆，其實就是完全二叉樹。最大堆要求節點的元素都要大于其孩子，最小堆要求節點元素都小于其左右孩子，兩者對左右孩子的大小關系不做任何要求，其實很好了解。有了上面的定義，我們可以得知，處于最大堆的根節點的元素一定是這個堆中的最大值。其實我們的堆排序算法就是抓住了堆的這一特點，每次都取堆頂的元素，将其放在序列最後面，然後将剩餘的元素重新調整為最大堆，依次類推，最終得到排序的序列。

步驟：

堆排序就是把堆頂的最大數取出,

将剩餘的堆繼續調整為最大堆,具體過程在第二塊有介紹,以遞歸實作

剩餘部分調整為最大堆後,再次将堆頂的最大數取出,再将剩餘部分調整為最大堆,這個過程持續到剩餘數隻有一個時結束

#_*_coding:utf-8_*_
__author__ = 'Alex Li'
import time,random
def sift_down(arr, node, end):
    root = node
    #print(root,2*root+1,end)
    while True:
        # 從root開始對最大堆調整

        child = 2 * root +1  #left child
        if child  > end:
            #print('break',)
            break
        print("v:",root,arr[root],child,arr[child])
        print(arr)
        # 找出兩個child中交大的一個
        if child + 1 <= end and arr[child] < arr[child + 1]: #如果左邊小于右邊
            child += 1 #設定右邊為大

        if arr[root] < arr[child]:
            # 最大堆小于較大的child, 交換順序
            tmp = arr[root]
            arr[root] = arr[child]
            arr[child]= tmp

            # 正在調整的節點設定為root
            #print("less1:", arr[root],arr[child],root,child)

            root = child #
            #[3, 4, 7, 8, 9, 11, 13, 15, 16, 21, 22, 29]
            #print("less2:", arr[root],arr[child],root,child)
        else:
            # 無需調整的時候, 退出
            break
    #print(arr)
    print('-------------')

def heap_sort(arr):
    # 從最後一個有子節點的孩子還是調整最大堆
    first = len(arr) // 2 -1
    for i in range(first, -1, -1):
        sift_down(arr, i, len(arr) - 1)
    #[29, 22, 16, 9, 15, 21, 3, 13, 8, 7, 4, 11]
    print('--------end---',arr)
    # 将最大的放到堆的最後一個, 堆-1, 繼續調整排序
    for end in range(len(arr) -1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, 0, end - 1)
        #print(arr)
def main():
    # [7, 95, 73, 65, 60, 77, 28, 62, 43]
    # [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
    #l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10]
    #l = [16,9,21,13,4,11,3,22,8,7,15,27,0]
    array = [16,9,21,13,4,11,3,22,8,7,15,29]
    #array = []
    #for i in range(2,5000):
    #    #print(i)
    #    array.append(random.randrange(1,i))

    print(array)
    start_t = time.time()
    heap_sort(array)
    end_t = time.time()
    print("cost:",end_t -start_t)
    print(array)
    #print(l)
    #heap_sort(l)
    #print(l)


if __name__ == "__main__":
    main()           

dataset = [16,9,21,3,13,14,23,6,4,11,3,15,99,8,22]

 for i in range(len(dataset)-1,0,-1):
     print("-------",dataset[0:i+1],len(dataset),i)
     #for index in range(int(len(dataset)/2),0,-1):
     for index in range(int((i+1)/2),0,-1):
         print(index)
         p_index = index

         l_child_index = p_index *2 - 1
         r_child_index = p_index *2
         print("l index",l_child_index,'r index',r_child_index)
         p_node = dataset[p_index-1]
         left_child =  dataset[l_child_index]

         if p_node < left_child:  # switch p_node with  left child
             dataset[p_index - 1], dataset[l_child_index] = left_child, p_node
             # redefine p_node after the switch ,need call this val below
             p_node = dataset[p_index - 1]

         if r_child_index < len(dataset[0:i+1]): #avoid right out of list index range
         #if r_child_index < len(dataset[0:i]): #avoid right out of list index range
             #print(left_child)
             right_child =  dataset[r_child_index]
             print(p_index,p_node,left_child,right_child)

             # if p_node <  left_child: #switch p_node with  left child
             #     dataset[p_index - 1] , dataset[l_child_index] = left_child,p_node
             #     # redefine p_node after the switch ,need call this val below
             #     p_node = dataset[p_index - 1]
             #
             if p_node < right_child: #swith p_node with right child
                 dataset[p_index - 1] , dataset[r_child_index] = right_child,p_node
                 # redefine p_node after the switch ,need call this val below
                 p_node = dataset[p_index - 1]

         else:
             print("p node [%s] has no right child" % p_node)


     #最後這個清單的第一值就是最大堆的值，把這個最大值放到清單最後一個， 把神剩餘的清單再調整為最大堆

     print("switch i index", i, dataset[0], dataset[i] )
     print("before switch",dataset[0:i+1])
     dataset[0],dataset[i] = dataset[i],dataset[0]
     print(dataset)