힙(Heap)이란?

힙(Heap)

완전 이진 트리의 일종으로 우선순위 큐를 구현하기 위해 사용하는 자료구조이다.

여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다.

최대 힙(Max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

key(ParentNode)>=key(ChildNode)

최소 힙(Min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

key(ParentNode)=<key(ChildNode)

힙 구현하기 (최소 힙 기준)

완전 이진 트리를 굳이 만들 필요 없다. 트리를 배열로 나타내도 충분하다‼️

루트 노드부터 번호를 매겨보면 다음과 같다.

• 루트 노드의 인덱스 = 1
• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
• 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
• 부모 노드의 인덱스 = 자식 노드의 인덱스 // 2

🔥 여기서 꼭 지켜줘야 할 것.

배열을 단순하게 선언하면 index가 0부터 시작한다.
그런데 루트 노드를 index 0으로 선언한 순간, 자식노드 부모노드의 관계를 인덱스로 표현할 수 없어진다.
⇒ 반드시 루트 노드의 index를 1로 설정하자!

힙의 삽입

1. 제일 마지막 단말 노드에 데이터를 삽입한다.
2. 부모 노드랑 계속 비교하면서 부모 노드가 자신보다 크다면 부모와 자신의 위치를 swap
3. 2번 조건을 만족하지 않을 때까지 또는 자신이 루트 노드가 아닐 때까지 반복한다.

heap = [0,2,3,5,4,7,6] 에 1 삽입하기

1. 제일 마지막 단말 노드에 데이터를 삽입한다.
   
2. 부모 노드랑 계속 비교하면서 부모 노드가 자신보다 크다면 부모와 자신의 위치를 swap

1. 2번 조건을 만족하지 않을 때까지 또는 자신이 루트 노드가 아닐 때까지 반복한다.

heap = [0,2,3,5,4,7,6]

def Insert(num) :
  # 1. 제일 마지막 단말 노드에 데이터를 삽입한다.
  heap.append(num)
  numIdx = len(heap)-1
  # 2. 부모 노드랑 계속 비교하면서 부모 노드가 자신보다 크다면 부모와 자신의 위치를 swap
  # 3. 2번 조건을 만족하지 않을 때까지 또는 자신이 루트 노드가 아닐 때까지 반복한다.
  while ((numIdx != 1) and (num < heap[numIdx//2])) :
    heap[numIdx], heap[numIdx//2] = heap[numIdx//2], heap[numIdx]
    numIdx = numIdx // 2
    print(heap)

Insert(1) 

# 출력 결과
[0, 2, 3, 1, 4, 7, 6, 5]
[0, 1, 3, 2, 4, 7, 6, 5]

힙의 삭제

1. 가져올 '최소값'을 미리 저장해준다.
2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.
3. 현재 노드에서 자식 노드와 비교 하면서 자식 노드가 더 작은 값이라면 Swap해준다.
4. 위치를 찾을 때 까지 3번 과정을 반복한다.

heap = [0, 1, 3, 2, 4, 7, 6, 5] 에서 최소값 삭제하기

1. 가져올 '최소값'을 미리 저장해준다.

1. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.
   1과 5의 위치가 바뀌었다.
   가장 마지막 노드와 루트 노드의 값을 바꿔주는 이유는 완전 이진 트리를 상태를 유지하기 위해서 이다. Swap이 끝났다면 이제 1은 더이상 하는 역할이 없으므로 pop 시켜줘도 된다!

1. 현재 노드에서 자식 노드와 비교 하면서 자식 노드가 더 작은 값이라면 Swap해준다.
   자식 노드는 두 개가 있다. 여기서 어떤 자식 노드를 선택해야 할까?
   지금은 최소 힙을 구현하는 과정이기 때문에, 두 자식 노드 중 더 작은 값을 가지는 노드를 위로 올리면 된다.

1. 위치를 찾을 때 까지 3번 과정을 반복한다.

heap = [0, 1, 3, 2, 4, 7, 6, 5]

def Delete(heap) :
  # 1. 가져올 '최소값'을 미리 저장해준다.
  result = heap[1]
  # 2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.
  heap[-1], heap[1] = heap[1], heap[-1]
  # 삭제할 값을 맨 뒤로 보냈으니, 삭제해준다.
  heap.pop()

  # 3. 현재 노드에서 자식 노드와 비교 하면서 자식 노드가 더 작은 값이라면 Swap해준다.
  # 4. 위치를 찾을 때 까지 3번 과정을 반복한다.
  parent = 1
  while (True) :
    child = parent * 2

    if (child+1 < len(heap) and heap[child] > heap[child+1]) : child += 1
    if (child >= len(heap) or heap[child] > heap[parent]) : break
    heap[child], heap[parent] = heap[parent], heap[child]
    parent = child
  print(result,heap)

Delete(heap)

힙, 왜 빠를까?

단순한 순차 탐색으로 최댓값, 최솟값을 찾을 경우 O(N)의 탐색 시간이 소요된다.

하지만, 힙의 경우 O(logN), 즉 트리의 높이만큼만 비교를 하게된다.

당연히 순차 탐색보다 빠를 수 밖에 없는 것이다.