파이썬 힙 heap 간단 구현 !!!

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리이다.

항상 최대의 값들이 필요한 연산이 있다면 힙을 사용하면된다,

 

힙은 항상 큰 값이 상위에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조이다.

다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다. 그러면 가장 큰 값은 모든 자식보다 커야하기 때문에 가장 위로 갈 것이다. 따라서 최대의 값들을 빨리 구할 수 있다,

 

 

맥스 힙의 원소 제거

최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.

스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없다.

또한 맥스 힙에 원소를 추가했던 것과 마찬가지로 원소를 삭제할 때도 힙의 규칙이 지켜져야한다.

 

아래와 같은 방법으로 하면 된다.

 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

3. 변경된 노드와 자식노들을 비교한다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 크다면 자리를 바꾼다.

4. 자식 노드 둘 보다 부모 노드가 크거가 가장 바닥에 도달하지 않을 때 까지 3. 과정을 반복한다.

4. 2. 에서 제거한 원래 루트 노드를 반환한다.

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        # 구현해보세요!
        # 왼쪽 자식 현*2
        # 오른쪽 자식 현*2 + 1
        # 부모 현//2
        list_1 =  self.items
        idx = len(list_1)
        list_1.append(value)
        while True:
            if idx > 1 and list_1[idx] > list_1[idx // 2]:
                list_1[idx], list_1[idx // 2] = list_1[idx // 2], list_1[idx]
                idx = idx // 2
                continue
            break

        return
    def delete(self):
        list_1 = self.items
        list_1[1] ,list_1[-1] = list_1[-1] ,list_1[1]
        max = list_1.pop()
        sigo_idx = len(list_1) - 1
        cur = 1
        while True:
            codomo_reft = cur * 2
            codomo_right = (cur * 2) + 1
            gt_idx = cur
            if codomo_reft <= sigo_idx and list_1[gt_idx] < list_1[codomo_reft]:
                gt_idx = codomo_reft
            if codomo_right <= sigo_idx and list_1[gt_idx] < list_1[codomo_right]:
                gt_idx = codomo_right

            if gt_idx == cur:
                break

            list_1[gt_idx], list_1[cur] = list_1[cur], list_1[gt_idx]
            cur = gt_idx
        return max

 먼저 원소 추가하는 방법은 마지막에 원소를 추가하고 나의 부모 노드와 비교하여 크면 바꾸고 작으면 바꾸지않는 방식이다. 원소 제거하는 방법이 조금 흥미로운데

먼저 제일큰 수와 제일 작은 수를 바꾼 뒤 pop을통해 제거해주고 그 값을 나중에 return해준다.

그리고 자식 노드와 비교를 하는데 먼저 왼쪽 자식과 비교한 뒤 왼쪽이 부모보다 크다면 gt_idx에 왼쪽 자식idx를 넣어주고 

또 한번 오른쪽 자식과 비교한다. 전의 if문분기를 탔다면 여기서 gt_idx에는 왼쪽의 자식의 idx과 비교를 하여 더 큰 값이 들어갈 것이다.

 

이렇게 비교하고 만약 if문을 타지 않았따면 cur과 gt와 같을것이다 이말은 자식보다 작지 않다는 뜻이므로 break를 해주어 탈출한다.

그게 아니라면 자식과 자리를 바꾸어주고 cur에 gt를 넣어준다.