StudyData Structure

MAX HEAP

MAX HEAP

  1. 완전이진트리
  2. 배열, heapsize(배열의 개수가 아닌 데이터의 개수)
  3. Priority Queue 때문에 구현한다.
  4. ADT
    1) is_empty() -> bool
    2) is_full() -> bool
    3) push(data) -> 반환없음
    4) pop() -> 삭제된 원소 반환
    5) top() -> 다음 번에 반환될 원소 반환

  • 첫번째 배열 자리는 쓰지 않고 구현(인덱스 0번 자리) - 책마다 다르다!

  • Heap property(push와 pop을 했을 때)
    1) 여전히 완전이진트리인가?
    2) 어떤 노드를 선택하든 key 값이 자식보다 작지 않다.(크거나 같다.)

  • 구현 방법
    1) heapsize++
    2) cur = Arr(heapsize)
    3) cur.key가 parent.key보다 크다면 cur와 parent 교환
    4) root node를 만날 때까지 진행

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
# 객체화 시켜주기 위해 Element class 선언
class Element:
    def __init__(self, key):
        self.__key = key

    @property
    def key(self):
        return self.__key

    @key.setter
    def key(self, k):
        self.__key = k

class MaxHeap:
    
    MAX = 1024
    
    def __init__(self):
        self.__heapsize = 0
        self.__container = [None for _ in range(MaxHeap.MAX)]

    # 부모 노드의 자리를 구할 때
    def __get_parent_idx(self, cur):
        return cur//2

    # 자식 노드의 왼쪽 자리를 구할 때
    def __get_left_child_idx(self, cur):
        return cur * 2

    # 자식 노드의 오른쪽 자리를 구할 때
    def __get_right_child_idx(self, cur):
        return cur * 2 + 1

    def is_empty(self):
        if self.__heapsize == 0:
            return True
        else:
            return False

    def is_full(self):
        if self.__heapsize == MaxHeap.MAX:
            return True
        else:
            return False

    def push(self, key):
        if self.is_full():
            raise IndexError("The heap is full.")

        self.__heapsize+=1
        cur_idx = self.__heapsize
        par_idx = self.__get_parent_idx(cur_idx)

        # cur_idx != root
        # key > container[parent].key
        while cur_idx != 1 and key > self.__container[par_idx].key:
            self.__container[cur_idx] = self.__container[par_idx]
            cur_idx = par_idx
            par_idx = self.__get_parent_idx(cur_idx)
        
        # Element는 객체를 만들기 위함
        # 처음에 키 값이 존재하지 않는다면 cur_idx !=1의 조건만 보고
        # 내려올 것이므로 뒤에 조건은 보지 않아서 에러가 발생하지 않는다.
        # 다음은 계속 Element 객체가 만들어진다.
        self.__container[cur_idx] = Element(key)

    # 자식 중에 큰 수를 구할 때
    def __get_bigger_child_idx(self, cur):

        left_child_idx = self.__get_left_child_idx(cur)
        right_child_idx = self.__get_right_child_idx(cur)

        if left_child_idx > self.__heapsize:
            return None
        elif left_child_idx == self.__heapsize:
            return left_child_idx
        else:
            left_child = self.__container[left_child_idx]
            right_child = self.__container[right_child_idx]
            if left_child.key > right_child.key:
                return left_child_idx
            else:
                return right_child_idx

    def pop(self):
        if self.is_empty():
            raise IndexError("The heap is empty.")

        ret = self.__container[1]

        temp = self.__container[self.__heapsize]

        cur_idx = 1

        bigger_child_idx = self.__get_bigger_child_idx(cur_idx)

        while bigger_child_idx and temp.key < self.__container[bigger_child_idx].key:
            self.__container[cur_idx] = self.__container[bigger_child_idx]
            cur_idx = bigger_child_idx
            bigger_child_idx = self.__get_bigger_child_idx(cur_idx)
        self.__container[cur_idx] = temp
        self.__heapsize -= 1

        # element를 줄 것인지 아니면 key값을 반환할 것인지를 선택하자.
        return ret.key
    
    def top(self):
        if self.is_empty():
            raise IndexError("The heap is empty.")

        return self.__container[1]

class PriorityQueue:
    def __init__(self):
        self.container = MaxHeap()

    # 래핑 함수(wrapping function)
    def enqueue(self, data):
        self.container.push(Element(data))

    def dequeue(self):
        return self.container.pop().key

# test code
if __name__ == "__main__":
    mh = MaxHeap()

    mh.push(10)
    mh.push(7)
    mh.push(6)
    mh.push(15)

    for idx in range(mh._MaxHeap__heapsize+1) :
        elem = mh._MaxHeap__container[idx]

        if elem:
            print(elem.key, end = " ")

    print()

    while not mh.is_empty():
        print(mh.pop(), end = " ")
Share