[백준11279] 최대 힙

문제:

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
1) 배열에 자연수 x를 넣는다.
2) 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
3) 프로그램은 처음에 비어있는 배열에서 시작하게 된다.
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제입력:

13
0
1
2
0
0
3
2
1
0
0
0
0
0

예제출력:

0
2
1
3
2
1
0
0

---

최대힙이란?

• 완전 이진 트리
• 부모 노드의 값이 언제나 자식 노드보다 같거나 크다
• 당연히 힙의 가장 큰 값은 루트노드가 된다
• 완전 이진 트리이기 때문에 구성해보면 자식 노드의 인덱스는 각각 (부모 노드 2 ), (부모노드2+1)가 된다

workflow

• 힙을 리스트에 보관 및 정의하다
• 리스트의 인덱스는 노드의 인덱스고, 리스트 인덱스별 밸류는 노드의 밸류다.
• 힙에 노드값을 넣고 빼기 위해서는 2가지 각각의 기능이 필요하다 insert랑 popout

    1: [10]
      /     \                                  1:  2:  3:
    2:[5]   3:[3]                => heap = [0, 10, 5, 3 ]

insert:

• 새로운 노드를 추가할때 가장 마지막 노드 = 즉 리스트의 가장 마지막에 배치한다
• 그리고 지금 위치의 부모 노드의 값이랑 비교한다. 부모 노드 인덱스는 parent_node_idx = (current_node_idx //2) 이다.
• 지금 노드값이 부모 노드값보다 크다면 부모노드랑 교환한다.
• 부모노드가 지금 노드가 된다.
• 교환이 더이상 안 일어날 때까지 반복한다.

heap =[0]
def exchange_with_parent(heap, current_idx):
    if current_idx<=1:
      return
    parent_idx = current_idx//2
    current_val = heap[current_idx]
    parent_val = heap[parent_idx]
    if current_val > parent_val:
        heap[current_idx], heap[parent_idx] = heap[parent_idx], heap[current_idx]
        exchange_with_parent(heap, parent_idx)



def insert(n):
  heap.append(n)
  current_idx = len(heap)-1
  exchange_with_parent(heap, current_idx)

for i in [1,3,5,8,7,32,2,1,3]:
  insert(i)
  print(heap)

pop-out

• 팝 아웃하고 싶은 위치의 노드를 pop한다.
• 마지막 노드 즉 리스트의 마지막 값을 팝 아웃한 곳에 넣는다.
• 자식 노드 중 큰 노드와 비교한다.10
• 자식 노드보다 지금 노드가 크기가 작다면 교환한다.
• 위치가 변경된 자식노드가 지금 노드가 된다.
• 교환이 더 이상 안 일어날 때까지 반복한다.

heap = [0, 32, 7, 8, 3, 5, 3, 2, 1, 1] 


def exchange_with_child(heap, current_idx):
  children_idx = [current_idx*2, current_idx *2+1]
  for child_idx in children_idx:
    if len(heap) < child_idx+1:
      return
    if heap[current_idx]< heap[child_idx]:
      heap[current_idx], heap[child_idx] = heap[child_idx], heap[current_idx]
      print(heap)
      exchange_with_child(heap, child_idx)

def pop_out():
  heap[1] = heap.pop()
  ## 여기서 run_exchange
  current_idx = 1
  exchange_with_child(heap , current_idx)
pop_out()```