Skip to content

Latest commit

 

History

History
156 lines (114 loc) · 5.88 KB

Heap.md

File metadata and controls

156 lines (114 loc) · 5.88 KB
Raw

Heap

Heap은 우선 순위 큐를 위하여 만들어진 비선형 자료구조이다.

우선순위 큐(Priority Queue)

우선순위 큐는 FIFO(First In First Out)인 일반 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 추상자료형*이다.
일반적으로 배열, 연결리스트, 힙 등으로 구현한다.

* 추상자료형(Abstract Data Type, ADT): 구현 방법을 명시하지 않고 자료구조의 특성과 연산을 명시한 것이다. Stack과 Queue 등이 해당한다.

ds-priority-queue2

javatpoint - priority queue

우선 순위 큐의 연산

  1. enqueue() : 새 요소 삽입
  2. dequeue() : 루트의 요소를 삭제하여 그 값을 반환
  3. peek() : 루트 요소를 반환

시간복잡도 비교

자료 구조 enqueue() dequeue()
배열 (unsorted array) O(1) O(N)
연결 리스트 (unsorted linked list) O(1) O(N)
정렬된 배열 (sorted array) O(N) O(1)
정렬된 연결 리스트 (sorted linked list) O(N) O(1)
힙 (heap) O(log N) O(log N)

힙(Heap)

힙은 노드가 왼쪽부터 채워지는 완전 이진 트리 형태를 가지며 우선순위가 높은 요소를 루트로 배치하고 항상 루트 요소가 먼저 나간다.
우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입 및 삭제 되는 시점에 바로 정렬된다.

종류

  • 최대 힙(Max Heap)
    • 루트가 가장 큰 값이 된다.
    • 부모 노드의 키 값이 자식 노드의 키 값과 같거나 큰 완전 이진 트리이다.
  • 최소 힙(Min Heap)
    • 루트가 가장 작은 값이 된다.
    • 부모 노드의 키 값이 자식 노드의 키 값과 같거나 작은 완전 이진 트리이다.

Min-Max-Heap


힙 요소 추가 push()

  1. 추가할 요소를 트리의 가장 마지막 정점에 입력한다.
  2. 추가한 요소가 부모 요소보다 우선순위가 높다면 부모와 순서를 바꾼다.
  3. 이를 반복하면 가장 우선순위가 높은 요소가 루트가 된다.

* 요소가 항상 마지막 정점에 추가되기 때문에 힙은 항상 완전 이진트리이며, 완전 이진트리의 높이는 log N이므로 힙의 요소 추가 알고리즘은 O(log N) 시간복잡도를 갖는다.

Push-min-heap


힙 요소 제거 pop()

  1. 루트 정점의 요소를 제거한다.
  2. 가장 마지막 정점의 요소를 루트로 올린다.
  3. 루트 요소의 두 자식 중 우선순위가 더 높은 정점과 바꾼다.
  4. 두 자식 요소의 우선순위가 더 낮을 때 까지 반복한다.

* 힙의 요소 제거 알고리즘은 추가와 동일하게 O(log N) 시간복잡도를 가진다.

Pop-min-heap


Heap의 응용

힙은 최대 최소 값을 빠르게 찾기를 원하거나 반복적으로 구하는 경우, Dijkstra의 최단 경로 알고리즘, 최소 신장 트리의 Prim 알고리즘 등의 그래프 알고리즘에서 유용하다. 또한 Heapsort 정렬 알고리즘과 Huffman 코딩(데이터 압축 기술)에도 사용된다.


Heap 구현

Min-Heap

이진 트리 형태로 구현해도 되고, 배열로 저장해도 된다.

파이썬에서는 heapq 모듈을 통해 heap 자료구조를 쉽게 사용할 수 있다.
heapq 모듈은 최소힙으로 구현되어있기 때문에 최대힙을 사용하려면 변환이 필요하다. (y=-x 변환)

import heapq
heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
result = heapq.heappop(heap)

자바스크립트에서는 직접 구현하여 사용해야한다.🥲

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  push(value) {
    this.heap.push(value);
    let currentIndex = this.heap.length - 1;
    let parentIndex = Math.floor(currentIndex / 2);

    while (parentIndex !== 0 && this.heap[parentIndex] < value) {
      swap(currentIndex, parentIndex);
      currentIndex = parentIndex;
      parentIndex = Math.floor(currentIndex / 2);
    }
  }

  pop() {
    const returnVlaue = this.heap[1];
    this.heap[1] = this.heap.pop();
    let currentIndex = 1;
    let leftIndex = 2;
    let rightIndex = 3;
    while (
      this.heap[currentIndex] < this.heap[leftIndex] ||
      this.heap[currentIndex] < this.heap[rightIndex]
    ) {
      if (this.heap[leftIndex] < this.heap[rightIndex]) {
        swap(currentIndex, rightIndex);
        currentIndex = rightIndex;
      } else {
        swap(currentIndex, leftIndex);
        currentIndex = leftIndex;
      }
      leftIndex = currentIndex * 2;
      rightIndex = currentIndex * 2 + 1;
    }
  }
}

Reference

🎨https://www.techiedelight.com/introduction-priority-queues-using-binary-heaps/
📄https://yoongrammer.tistory.com/81
📄https://www.javatpoint.com/ds-priority-queue 📄https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 📄C언어로 쉽게 풀어쓴 자료구조