Heap 알고리즘 정리

1️⃣ 우선순위 큐(Priority Queue)의 원리

2️⃣ 완벽한 이진트리의 형태

3️⃣ 시간 복잡도 O(nlogn)

 

Keyword : Maxheap(부모노드 > 자식노드), Minheap(부모노드 < 자식노드)

 

하나씩 꺼낼 때마다 부모 노드와 비교하여

Maxheap이면 → 부모 노드보다 자식 노드가 크면 swap

Minheap이면 → 부모 노드보다 자식 노드가 작으면 swap

 

코드 구현

arr = [4,7,8,1,5,3,6,9] # Maxheap
heap = [0]*20
hindex = 1 # 힙이라는 1차 배열의 인덱스 역할

def insert(value):
    global heap, hindex
    heap[hindex] = value
    now = hindex
    hindex+=1

    while 1:
        parents = now//2 # 부모인덱스 확인
        if parents == 0: break
        if heap[parents] > heap[now]: break
        heap[parents], heap[now] = heap[now], heap[parents] # 자식이 더 크면 스왑
        now = parents # 부모의 부모와 비교

def top():
    global heap
    return heap[1] # 루트노드 리턴

def pop():
    global heap, hindex
    heap[1] = heap[hindex-1]
    heap[hindex] = 0
    hindex -= 1

    now = 1
    while 1:
        son = now*2 # 왼쪽 자식
        rson = son+1 # 오른쪽 자식
        # 오른쪽에 자식이 있고, 왼쪽이랑 오른쪽이랑 비교 결과 오른쪽이 더 크다면 자식을 오른쪽 자식으로 찜
        if heap[rson] != 0 and heap[son] < heap[rson]: son = rson
        if heap[now] >= heap[son]: break # >=인 이유 -> 둘 다 0일 때 고려
        heap[now], heap[son] = heap[son], heap[now]
        now = son # 자식의 자식이랑 비교

for i in range(len(arr)):
    insert(arr[i]) # 트리의 형태로 저장 (1차 배열)
print(heap)

for i in range(len(arr)):
    print(top(), end=' ')
    pop() # 맨 뒤에 있는 아이를 1번 인덱스로 올리고 자식들이랑 비교