forked from wangzheng0822/algo
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_heap_sort.py
More file actions
47 lines (34 loc) · 962 Bytes
/
binary_heap_sort.py
File metadata and controls
47 lines (34 loc) · 962 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/python
# -*- coding: UTF-8 -*-
from binary_heap import BinaryHeap
class BinaryHeapSort(BinaryHeap):
def __init__(self):
super(BinaryHeapSort, self).__init__()
def sort(self, nums):
"""
排序
1. 堆化，大顶堆
2. 排序，从后往前遍历，首尾元素互换，子数组堆化
:param nums:
:return:
"""
assert type(nums) is list
length = len(nums)
if length <= 1:
return
self._type_assert(nums)
# heapify
self._heapify(nums, length-1)
# sort
for i in range(length-1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
self._heap_down(nums, 0, i-1)
return
if __name__ == '__main__':
bhs = BinaryHeapSort()
nums = [3, 5, 2, 6, 1, 7, 6]
print('--- before sort ---')
print(nums)
bhs.sort(nums)
print('--- after sort ---')
print(nums)