Data-Structures-and-Algorithms/heap.py at master · Fieldhunter/Data-Structures-and-Algorithms · GitHub

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
"""
@version: python3.6
@author: Fieldhunter
@contact: 1677532160yuan@gmail.com
@time: 2020-05-03
"""
# implement a large top heap
class Heap():
    def __init__(self):
        self.__data = [None]

    def add_data(self, element):
        self.__data.append(element)
        index = len(self.__data) - 1
        while index > 1:
            if self.__data[index] > self.__data[index//2]:
                self.__data[index], self.__data[index//2] = \
                    self.__data[index//2], self.__data[index]
                index //= 2
            else:
                break

    def del_top_element(self):
        num = len(self.__data) - 1
        if num == 0:
            print("No data in Heap")
        else:
            self.__data[num], self.__data[1] = self.__data[1], self.__data[num]
            del self.__data[-1]
            num -= 1
            heap_up_down(self.__data,num)

    def return_top_data(self):
        return self.__data[1]


# heap up from top to bottom
def heap_up_down(data, num, index=1):
    while (2*index) <= num:

        # both child nodes exist
        if (2*index+1) <= num:
            if data[2*index] > data[index]:
                if data[2*index+1] > data[index]:
                    if data[2*index] > data[2*index+1]:
                        data[index], data[2*index] = data[2*index], data[index]
                        index *= 2
                    else:
                        data[index], data[2*index+1] = data[2*index+1], data[index]
                        index = 2 * index + 1
                else:
                    data[index], data[2*index] = data[2*index], data[index]
                    index *= 2
            elif data[2*index+1] > data[index]:
                data[index], data[2*index+1] = data[2*index+1], data[index]
                index = 2 * index + 1
            else:
                break

        # only left child node exist
        else:
            if data[2*index] > data[index]:
                data[index], data[2*index] = data[2*index], data[index]
                index *= 2
            else:
                break


def heap_sort(data):
    data.insert(0, None)
    num = len(data) - 1
    pointer = num // 2

    # build heap
    while pointer >= 1:
        heap_up_down(data, num, pointer)
        pointer -= 1

    # sort
    index = num
    for _ in range(num-1):
        data[1], data[index] = data[index], data[1]
        index -= 1
        heap_up_down(data, index)

    del data[0]