[자료구조💾] 7장 최대 힙

교재 : 파이썬으로 배우는 자료구조 프로그래밍 (유석종, 휴먼싸이언스)

 

7.1 최대 최소힙

1) 최대 힙 (max heap)

- 최대 트리 (max tree) : 이진 트리에서 각 노드의 키 값이 그 자식 노드보다 큰 트리

- 최대 힙: 최대 트리의 조건을 만족하는 완전 이진 트리

- 루트에 전체 노드의 최댓값이 저장되므로 최대값을 탐색하는 데 유용하다.

2) 최소 힙 (min heap)

- 최소 트리 (min tree) : 각 노드 값이 그 자식 느도보다 작은 트리

- 최소 힙 : 최 소 트리이면서 완전 이진 트리 조건을 만족하는 경우

- 루트에 전체 노드의 최솟값이 저장된다.

 

3) 최대 힙에 노드 추가

- 최대 트리와 완전 이진 트리의 조건을 모두 만족해야 한다.

• 완전 이진 트리의 조건을 만족하기 위해 노드는 트리의 마지막 위치에 삽입하는 것이 좋다.
• 최대 트리 조건을 만족하기 위해 새 노드가 올바른 위치를 찾을 때까지 상위 노드와 반복적으로 비교한다.

- 알고리즘

1. 최대 힙의마지막 노드 다음에 새로운 노드를 추가한다.
2. 새 노드와 그 부모 노드의 크기를 비교하여 새 노드가 더 크다면 부모 노드와 위치를 교환(swap)한다.
3. 새 노드가 올바른 위치를 찾거나 루트에도달할 때까지 2번 과정을 반복한다.

 

4) 최대 힙에서 노드 삭제

- 최대 값인 루트 노드의 삭제를 뜻한다.

- 방법 : 마지막 노드를 루트 위치로 이동하여 완전 이진 트리 조건을 만족시키는 것

- 새 루트 노드가 최대 트리 조건을 만족하도록 하위노드와 비교하여 재구성한다.

- 시간 복잡도(트리 높이에 비례) :  O(log2n)

- 알고리즘

1. 루트 값을 반환할 변수에 복사하고, 마지막 노드를 루트 위치로 이동한다.
2. 새 루트의 좌우 자식 노드 중 큰 값을 비교 노드로 선택한다.
3. 새 루트와 선택한 자식 노드를 비교하여 새 루트가 더 크면 재구성을 종료한다.
4. 자식 노드가 새 루트보다 더 크면 교환(swap)하고, 하위 레벨에서 2번 과정을 반복한다.

 

5) 최대 힙에서 노드 추가와 삭제 코드

class Heap:
  def __init__(self, size):
    self.size = size
    self.heap = [None]*size
    self.count = 0

  def __str__(self):
    return "Heap, 0 is dummy"
  
  def isEmpty(self):
    return self.count == 0
  
  def isFull(self):
    return self.size-1 == self.count
  
  def add_heap(self, item):
    if self.isFull():
      return
    self.count += 1
    i = self.count
    while i!=1 and item > self.heap[i//2]:
      self.heap[i] = self.heap[i//2]
      i //= 2
    self.heap[i] = item
    print("%2d " %item, end = ' ')
    print(self.heap)

  def del_heap(self):
    if self.count == 0:
      print("Empty Heap")
      return
    item = self.heap[1]
    temp = self.heap[self.count]
    self.heap[self.count] = None
    self.count -= 1

    parent = 1
    child = 2

    while child <= self.count:
      if child < self.count and self.heap[child] < self.heap[child+1]:
        child += 1
      if temp >= self.heap[child]: 
        break
      self.heap[parent] = self.heap[child]
      parent = child
      child *= 2
    if self.count!=0:
      self.heap[parent]=temp
    return item

 

 

7.2 우선 순위 큐

1) 우선 순위 큐

- 큐에 대기 중인 작업(job)을 도착 순서가 아니라 작업의 우선순위(priority)에 따라 처리하는 큐

- 운영체제의 작업 스케줄링(job scheduling) 등에 활용된다.

- 구현 방법

• 비 정렬 선형 리스트
• 정렬 선형 리스트
• 최대 힙

 

2) 비 정렬 선형 리스트(unsorted list)

- 작업이 리스트에 추가될 때 우선순위를 고려하지 않고 도착 시간대로 가장 뒤에 추가한다.

- 리스트에서 삭제할 때는 도착 순서가 아니라 우선 순위가 높은 작업이 먼저 삭제된다.

- 작업 추가 시간 복잡도 : O(1)

- 삭제 시간 복잡도 : O(n)

 

3) 정렬 선형 리스트 (sorted list)

- 큐에 작업을 추가하는 시점에 우선 순위를 고려하여 큐 안의 작업들을 정렬한다.

- 삭제할 때는 우선순위가 높은 작업이 정렬 없이 바로 제거된다.

- 작업 추가 시간 복잡도 : O(n)

- 삭제 시간 복잡도 : O(1)

 

4) 최대 힙

- 우선 순위 큐를 구현하기에 가장 적합한 자료구조

- 루트가 큐에서 삭제되면 재구성 과정이 수행된다.

- 최대 힙에서 작업의 추가와 삭제에 걸리는 시간(최대 힙의 높이) : O(logn2)에 비례한다.

 

 

7.3 힙 정렬

1) 힙 정렬 (heap sort)

- 최대 힙(max heap)의 루트가 전체 원소의 최댓값이라는 사실을 이용해 정렬을 수행한다.

- 최대 힙에서 루트(최댓값)을 반복적으로 제거하여 정렬 리스트로 이동시키고 남은 원소들을 가지고 다시 최대 힙으로 재구성한다.

- 시간 복잡도 : 최대 힙의 재구성 시간(O(log₂n)) * 반복횟수(원소 수=n) = O(nlog₂n)

- 최대 힙 재구성

1. 노드 i의 자식 노드(2i, 2i+1) 중 큰 값을 선택하여 비교한다.
2. 노드 i가 자식 노드보다 큰 경우 알고리즘을 종료한다.
3. 자식이 큰 경우 두 원소를 교환하고, 그 하위 레벨에서 1번을 반복한다.
4. 하위 자식 노드가 존재하지 않으면 알고리즘을 종료한다.

 

2) 코드로 구현하기

class HeapSort:
  def __init__(self, num):
    self.num = num
    self.size = len(num)
    print("Heap Sort", self.num)

  def __str__(self):
    for i in range(self.size):
      print("%2d " % self.num[i])

  def swap(self, a, b):
    temp = self.num[a]
    self.num[a] = self.num[b]
    self.num[b] = temp

  def makeHeap(self, root, n):
    temp = self.num[root]
    child = 2 * root
    while child <= n:
      if child < n and self.num[child] < self.num[child+1]:
        child += 1
      if temp > self.num[child]:
        break
      else:
        self.num[child//2] = self.num[child]
        child *= 2
    self.nu[child//2] = temp
  
  def sort(self):
    n = self.size - 1
    for i in range(n//2, 0, -1):
      self.makeheap(i, n)
    
    print(self.num)
    for i in range(n-1, 0, -1):
      self.swap(1, i+1)
      self.makeHeap(1,i)
      print(self.num)