Table of Contents

정렬이란?

임의로 나열되어 있는 데이터들을 주어진 항목에 따라 크기 순서대로 작은 순서부터 (오름차순) 또는 큰 순서부터 (내림차순) 늘어놓은 것임
정렬되어 있는 데이터들은 다음과 같은 작업을 수행할 때 응용
① 데이터를 탐색할 때
② 리스트에 있는 다른 항목들을 비교할 때

분할 정복 Divide and Conquer

more learn
분할 정복은 말 그대로 문제를 ‘분할’ 해서 ‘정복’ 한 다음 정답을 ‘조합’해 나간다는 의미

분할 정복은 재귀를 활용하는 대표적인 알고리즘

힙 Heap

힙: 힙의 특성(최소 힙 Min Heap 에서는 부모가 항상 자식보다 작거나 같다)을 만족하는 거의 완전한 트리 Almost Complete Tree 인 특수한 트리 기반의 자료구조

트리 기반의 자료구조
heapq 모듈: 힙으로 구현 되어 있음
그중에서도 파이썬에는 최소 힙만 구현되어 있음

루트가 가장 작은 값

최소 힙: 부모가 항상 자식보다 작기 때문
우선순위 큐: 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현됨

기반 구현

우선순위 큐 ADT(추상 자료형): 주로 힙으로 구현
힙: 주로 배열로 구현
-> 따라서 우선순위 큐는 결국은 배열로 구현하는 셈

[구현 예시]
A = [2,7,26,25,19,17,1,90,3,36]
111

[주의]
여기서 오해하기 쉬운 특징 중 하나는 힙은 ~~정렬된 구조~~ 가 아님

최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐, 서로 정렬되어 있지 않다.
- ex) 오른 쪽의 자식 노드가 레벨 차이에도 불구하고, 왼쪽 노드보다 더 작은 경우도 얼마든지 있을수 있다.
- 부모, 자식 간의 관계만 정의할 뿐, ~~좌우에 대한 관계~~는 정의하지 않기 때문이다 (최소 힙)
부모는 항상 자식보다 작을 뿐, ~~좌우의 정렬~~ 관계는 제각각

이진 힙 Binary Heap

자식이 둘인 힙
대부분은 이진 힙이 널리 사용됨

트리 중에서 이진 트리가 널리 사용되는 이유와 비슷

힙은 완전 이진 트리이기 때문에 배열에 순서대로 표현하기에 적합

[빈틈없이 배치]

완전 이진 트리 형태인 이진 힙은 배열: 빈틈없이 배치가 가능
대개 트리의 배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용

활용

힙은 항상 균형을 유지하는 특징 때문에 다양한 분야에 널리 활용된다.

대표적으로 우선 순위 큐뿐만 아니라 이를 이용한 다익스트라 알고리즘에도 활용된다.
힙 덕분에 다익스트라 알고리즘의 시간 복잡도는 O(\(V^2\))에서 O(Elog V)로 줄어들 수 있음.
이외에도 원래의 용도인 힙 정렬과 최소 신장 트리 Minimum Spanning Tree 를 구현하는 프림 알고리즘 Prim’s Algorithm에 활용
중앙값의 근사값 Approximation 을 빠르게 구하는 데도 활용

중앙 근사값 노드 추출 용이

부모, 자식 관계가 정의되어 있는 완전 이진 트리이기 때문에 적절히 중간레벨의 노드를 추출하면 중앙값에 가까운 값을 정확하지는 않지만 근사치로 빠르게 추출 가능

힙 연산

이진 힙 구현을 위한 클래스 정의

파이썬의 heapq 모듈에서 지원하는 최소힙 연산을 여기서는 파이썬의 리스트만으로 동일하게 구현

class BinaryHeap(object):
  def __init__(self):
    //  0번 인덱스는 사용하지 않기 위해 None 을 미리 설정 해둠
    // 대개 트리의 배열 표현의 경우 인덱스 계산을 편하게 하기 위해 인덱스는 1부터 사용
    // 특히 이진 힙에서는 항상 1번 인덱스부터 사용
    self.items = [None]

  def __len__(self):
    return len(self.items) - 1

클래스의 뼈대를 만듦
len() 메소드
- len() 으로 호출하면 마지막 요소의 인덱스를 가져오기 위해 실제 길이보다 하나 더 작은 값을 가져오도록 재정의함

[추가 상식]
len() 처럼 밑줄( _ ) 2개로 둘러싸인 함수

파이썬의 매직 메소드로 여러 가지 내부 Built-In 기능이 동작되는 데 사용 됨
예를 들어 len(a) 를 하게 되면, 내부적으로 a.len() 을 호출하여 이 결과를 리턴

삽입

업힙 Up-Heap 연산: 힙에 요소를 삽입 시 필요

일반적으로 업힙 연산은 percolate_up() 이라는 함수로 정의.

[힙에 요소를 삽입하는 과정]

요소를 가장 하위 레벨의 최대한 왼쪽으로 삽입한다(배열로 표현할 경우 가장 마지막에 삽입한다).
부모 값과 비교해 값이 더 작은 경우 위치를 변경한다.
계속해서 부모 값과 비교해 위치를 변경한다(가장 작은 값일 경우 루트까지 올라감).
- 이 그림에는 신규 아이템 7 이 마지막에 삽입되어, 부모 노드의 값과 비교하면서 점점 스왑
- 두 번째 스왑 이후에야 부모 노드인 5 보다 더 크기 때문에 더 이상 스왑되지 않고 멈춤

[삽입 예시]
A = [2,7,26,25,19,17,1,90,3,36] 에 ‘37’ 삽입

코드 구현

def _percolate_up(self):
  i = len(self) 
  parent = i // 2 
  while parent > 0:
    if self.items[i] < self.items[parent]:
      self.items[parent], self.items[i] = self.items[i], self.items[parent] 
    i = parent 
    parent = i // 2
  
  def insert(self, k):
    self.items.append(k) 
    elf._percolate_up()

insert() 함수: 삽입 실행
- insert() 함수의 self.items.append(): 1번 과정
percolate_up() 함수: 2번, 3번 과정
- 이 과정을 통해 7 은 5 보다는 크기 때문에 루트까지는 될 수 없고
- 계속 스왑되다가 두 번째 레벨에 안착하게 됨.
- percolate_up() 함수명 앞에는 내부 함수라는 의미로 PEP 8 기준과 관례에 따라 밑줄( _ )을 부여해서 _percolate_up() 으로 정함

시간 복잡도

O(log n)

_percolate_up() 함수: parent 를 i // 2 로 약 절반씩 줄여나가는 형태
- 로그만큼 연산을 수행

추출

추출 자체는 매우 간단하다. 루트를 추출하면 된다.

추출 이후에 비어 있는 루트: 가장 마지막 요소가 올라감
다운힙 Down-Heap 연산: 이번에는 반대로 자식 노드와 값을 비교해서 자식보다 크다면 내려감

[추출 예시]
A = [2,7,26,25,19,17,1,90,3,36] 에 루트인 ‘90’ 추출

구현

percolate_down() 이라는 이름의 함수로 구현

수도코드

Max-Heapify (A, i):
  left ← 2×i 
  right ← 2×i + 1
  largest ← i

  if left ≤ heap_length[A] and A[left] > A[largest] then:
    largest ← left

  if right ≤ heap_length[A] and A[right] > A[largest] then:
    largest ← right

  if largest ≠ i then:
    swap A[i] and A[largest] 
    Max-Heapify(A, largest)

인덱스가 1 이상일 때만 동작하도록 구현되어 있음
- 첫 번째 항목(0번 인덱스)은 항상 비워두고 1번 인덱스부터 사용하는 이유는 인덱스 계산을 편하게 하기 위함임.
- 특히 1번 인덱스부터 사용하게 되면 인덱스 계산이 깔끔 하게 떨어짐
- 이런 경우는 머신러닝 분야에서도 종종 볼 수 있다.
  - 경사하강법 Gradient Descent 에서 기울기를 계산할 때 미분이 깔끔하게 떨어지도록 일부러 상수항을 부여하기도 함.

[이진 힙에서 인덱스를 1부터 시작하는 경우에는 어떻게 계산이 될까?]
부모, 자식 노드의 인덱스를 계산 가능
(이진 힙의 인덱스 위치 계산 수도코드)

Parent(i) 
  return ceil((i - 1) / 2)
Left(i) 
  return 2i
Right(i) 
  return 2i + 1

부모 노드를 구하는 코드: 2를 나눈 올림값
자식 노드: 왼쪽, 오른쪽 각각이 i * 2 , i * 2 + 1 로 깔끔하게 계산이 처리됨

파이썬 구현

이처럼 깔끔한 계산을 위해 1번 인덱스부터 사용하며, 0번 인덱스는 비워두는 것.

참고로 여기서 수도코드는 최대 힙(부모노드가 더 큰 것)이다.
우리가 구현하려는 것은 최소 힙이므로 이 부분은 수도코드의 알고리즘을 적절히 수정해 다음과 같이 구현가능

def _percolate_down(self, idx):
  left = idx * 2
  right = idx * 2 + 1
  smallest = idx

  if left <= len(self) and self.items[left] < self.items[smallest]:
    smallest = left

  if right <= len(self) and self.items[right] < self.items[smallest]:
    smallest = right

  if smallest != idx:
    self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx] self._percolate_down(smallest)

def extract(self):
  extracted = self.items[1] 
  self.items[1] = self.items[len(self)] 
  self.items.pop() 
  self._percolate_down(1) 
  return extracted

extract() 함수: 추출 함수
이후 루트 값이 추출되고,
percolate_down() 이 실행: 여기서는 최소 힙이므로 변수명도 smallest 로 변경
- 각각 왼쪽과 오른쪽 자식을 비교하고 더 작다면 해당 인덱스로 교체.
인덱스가 교체되었다면 서로 값을 스왑하고 다시 재귀 호출
- 값이 스왑되지 않을 때까지 계속 자식 노드로 내려가면서 스왑될 것이다. 즉 힙 특성이 유지될 때까지 계속 반복해서 재귀 호출된다.

시간복잡도

그렇다면 시간 복잡도는 O(1)이라고 생각할 수 있겠지만,
추출 이후에 다시 힙의 특성을 유지하는 작업이 필요하기 때문에 시간 복잡도는 O(log n)이다.

전체 코드

class BinaryHeap(object): 
  def __init__(self):
    self.items = [None]

  def __len__(self):
    return len(self.items) - 1

  # 삽입 시 실행, 반복 구조 구현 
  def _percolate_up(self):
    i = len(self) 
    parent = i // 2 
    while parent > 0:
      if self.items[i] < self.items[parent]:
        self.items[parent], self.items[i] = self.items[i], self.items[parent] 
      i = parent parent = i // 2

  def insert(self, k):
    self.items.append(k) 
    self._percolate_up()

  # 추출시 실행, 재귀 구조 구현 
  def _percolate_down(self, idx):
     left = idx * 2
     right = idx * 2 + 1
     smallest = idx

    if left <= len(self) and self.items[left] < self.items[smallest]:
      smallest = left
    
    if right <= len(self) and self.items[right] < self.items[smallest]:
      smallest = right
    
    if smallest != idx:
      self.items[idx], self.items[smallest] = self.items[smallest], self.items[idx] 
      self._percolate_down(smallest)

  def extract(self):
      extracted = self.items[1] 
      self.items[1] = self.items[len(self)] 
      self.items.pop() 
      self._percolate_down(1) 
      return extracted

기존 파이썬 heap 모듈

heapq.heappush() 는 insert()에 대응
heapq.heappop() 은 extract()에 대응

이처럼 이진 힙의 연산에 각각 대응되는 함수를 모두 구현

[참고]
이진 힙 vs 이진 탐색 트리(BST)

힙: 상/하 관계를 보장하며
- 특히 최소 힙에서는 부모가 항상 자식보다 작음
- 가장 큰 값을 추출하거나(최대 힙) 가장 작은 값을 추출하 려면(최소 힙) 이진 힙을 사용
  - 이진 힙은 이 작업이 O(1)에 가능
  - 우선순위와 연관되어 있으며 따라서 이진 힙은 우선순위 큐에 활용된다.
BST: 좌/우 관계를 보장.
- BST에서 부모는 왼쪽 자식보다는 크며, 오른쪽 자식보다는 작거나 같다.
- 이 같은 특징으로 인해 BST는 탐색과 삽입 모두 O(log n)에 가능하며, 모든 값이 정렬되어야 할 때 사용한다.

힙 정렬을 사용한 출력

[추출 예시]
A = [2,7,26,25,19,17,1,90,3,36]

2323

Coding test

[032] Algorithm(정렬4_분할정복 Divide and Conquer: 힙정렬 Heap Sort)

04 Feb 2020

목차