(Pyhton/Heap) 힙 (Heap)

 Heap :이진 트리의 한 종류

• 루투 노드가 언제나 최댓값, 최솟값
•  완전 이진 트리여야함 (레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진트로 , k-1 에서는 노드가 순차적)
•  

완전이진트리

maxheap, minheap    이진탐색트리와의 비교

1, 완전한 크기순인가 >> 아니다

2. 빠르게 검색할 수 있는가 >> 아니다 >>

3. 부가 제약조건? >> 완전이진트리 여야함

 

 

최대힙 (Max Heap)

• __init__() : 빈 최대힙 생성
• insert(item) -  새로운 원소 삽입
• remove() 최대 원소를 반환 (root node) >> 동시에 삭제

표현 (배열 이용) 

왼쪾 자식의 번호 : 2*m , 오른쪽은 2*m +1 부모 m // 2 

노드 마지막 노드에서만 삭제/추가 가능

 

 

insert 구현

class MaxHeap:

    def __init__(self):
        self.data = [None]


    def insert(self, item):
        self.data.append(item)

        i = len(self.data)-1

        while self.data[i//2]: # 부모가 있으면
            if self.data[i//2] < self.data[i]: # 자식이 부모보다 크면
                self.data[i//2], self.data[i] = self.data[i], self.data[i//2] # 바꿔저장하고
                i = i//2 # 위로 한번 더 올라감
            else: # 알맞게 감 
                break


def solution(x):
    return 0

 

remove 구현

 

def remove(self):
    # 하나이상의 노드가 존재하는 경우
    if len(self.data) > 1:
        # 맨마지막 원소와 위치바꾸기
        self.data[1], self.data[-1] = self.data[-1], self.data[1]
        data = self.data.pop(-1)
        self.maxHeapify(1)
    else:
        data = None
    return data

 

 

최대힙 원소 삭제후 최신화 구현

def maxHeapify(self, i):
    # i는 어느 기준으로 바꿀건가

    # 왼쪽 자식 (left child) 의 인덱스를 계산합니다.
    left = i * 2
    # 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
    right = i * 2 + 1
    greatest = i

    # 자신(i), 왼쪽자식(left), 오른쪽자식(right) 중 최대를 찾아서 이것의 인덱스를 smallest에 담는다
    # 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
    if left < len(self.data) and self.data[left] > self.data[greatest]:
        # 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
        greatest = left

    # 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
    if right < len(self.data) and self.data[right] > self.data[greatest]:
        # 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
        greatest = right

    # 만약 이 인덱스가 i와 같지 않다면 자식들 중에 나보다 큰 키값을 가진 노드가 발견된 경우
    if greatest != i:
        # 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
        self.data[i], self.data[greatest] = self.data[greatest], self.data[i]
        # 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
        self.maxHeapify(greatest)