# Algorithm_Sort_Heap srot ###### tags: `Algorithms` `Sort` `python` ```python def heapify(input_array, index, bound): """將資料結構化為heap parameters: input_array: 輸入的未排序陣列 index: 要排序的root bound: 比較邊界，如果某個root的左、右索引已超過陣列長度就不處理 假設，root的index=n，那其節點索引為 root: n root_left_node: 2n + 1 root_right_node: 2n + 2 舉例來說，[0, 1, 2, 3, 4, 5, 6] 0 1 2 3 4 5 6 0為root，左邊節點為1，右邊則為2 1為root，左邊節點為3，右邊則為4 heap sort的一半是最後的節點，因此只會比較到陣列一半取上高斯 其餘皆會是最終節點，不需要再比較，所以3456本身是不需要比較的 我們會從2開始比，也就是7/2 = 3 - 1 = 2(因為python的索引初始值為0) 要記得，python的索引是由0開始 root永遠是三個節點中最大的(或最小的)，但節點不考慮大小 5 5 1 2 2 1 左邊兩種情況都可以 """ # 先預設最大值為root index largest_idx = index # print(f'init_array: {input_array}') # print(f'init_larget_idx: {largest_idx}, value: {input_array[largest_idx]}') left_idx = index * 2 + 1 # print(f'left_idx: {left_idx}') right_idx = index * 2 + 2 # print(f'right_idx: {right_idx}') # 下面的比較，因為我們只關心root是最大的，因此不需要再比較左右兩邊 # 注意到與陣列長度的比較條件必需在前面，不然會引發索引異常 if left_idx < bound and input_array[largest_idx] < input_array[left_idx]: largest_idx = left_idx # print(f'l_larget_idx: {largest_idx}, value: {input_array[largest_idx]}') if right_idx < bound and input_array[largest_idx] < input_array[right_idx]: largest_idx = right_idx # print(f'r_larget_idx: {largest_idx}, value: {input_array[largest_idx]}') # 比較之後，如果最大值的異動，那就調整array的順序 if largest_idx != index: input_array[index], input_array[largest_idx] = input_array[largest_idx], input_array[index] # print(f'new array: {input_array}') # 遞迴處理heapify heapify(input_array, largest_idx, bound) def heap_sort(input_array): """heap sort""" array_size = len(input_array) # heap sort會從底層開始排序上來 # 而且並不會所有的元素都排序，因為n//2 + 1之後的節點都是最終節點 # 只有n//2 + 1之前是root，因此只做這邊的迴圈比較 # 這邊只是做heap的結構 for i in range(array_size // 2 - 1, -1, -1): heapify(input_array, i, array_size) # 處理排序 # 我們知道，經過heap過的結構，最大的一定是在最上面(假設是max heap) # 因此，實作上會將root的部份跟最後的結點做交換，再將n-1做一次heap for i in range(array_size - 1, 0, -1): # 每次heap之後都做頭尾的交換 # print(f'heap_sort: {input_array}') input_array[0], input_array[i] = input_array[i], input_array[0] # 特別注意到，每一次迭代都會減少一個，因此這邊給的是迴圈中的i，而不是array_size heapify(input_array, 0, i) return input_array ``` 下面給出五個資料集在不同資料量下的結果，其中 * l1: 已經排序好的，由小到大 * l2: 已經排序好的，但是逆排序，由大到小 * l3: 亂數生成 * l4: 亂數生成 * l5: 亂數生成 | Heap Sort | 20000 | 40000 | 60000 | 80000 | 100000 | |----------- |-------- |-------- |-------- |-------- |-------- | | l1 | 416 ms | 606 ms | 864 ms | 1.23 s | 1.51 s | | l2 | 255 ms | 721 ms | 876 ms | 1.15 s | 1.64 s | | l3 | 265 ms | 603 ms | 923 ms | 1.23 s | 1.8 s | | l4 | 297 ms | 562 ms | 946 m | 1.16 s | 1.59 s | | l5 | 279 ms | 553 ms | 966 ms | 1.22 s | 1.66 s |