[알고리즘] Heapsort

자료구조 Heap

• 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조입니다.
• 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조입니다.

자세한 내용은 해당 Post를 참조해주세요.

[자료구조] Heap

Heapsort

• 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
• 과정 설명
  
  • 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
    
    • 내림차순을 기준으로 정렬
  • 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
  • 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

Heapsort 구현

• 힙(heap)은 1차원 배열로 쉽게 구현될 수 있다.
• 정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입한다.
• 최대 힙으로 구성된 배열에서 최댓값부터 삭제한다.

최소 힙의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

최소heap의 삽입 과정

최소 힙의 삭제(참조)

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
   
   • 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재구성한다.

Heapsort Typescript 구현 예제

lass MinHeap {
  public heap: number[];
  constructor() {
    this.heap = [];
  }

  // 부모 인덱스, 자식 인덱스 구하는 메소드
  getParentIndex(childIndex: number): number {
    return Math.floor((childIndex - 1) / 2);
  }
  getLeftChildIndex(parentIndex: number): number {
    return 2 * parentIndex + 1;
  }
  getRightChildIndex(parentIndex: number): number {
    return 2 * parentIndex + 2;
  }

  swap(idx_1: number, idx_2: number): number[] {
    [this.heap[idx_1], this.heap[idx_2]] = [this.heap[idx_2], this.heap[idx_1]];
    return this.heap;
  }
  size(): number {
    return this.heap.length;
  }

  // 최소 값 추출 메서드
  pop(): number | null {
    // 배열에 아무것도 없다면 null을 return 진행
    if (this.heap.length === 0) return null;
    // 최소값 확인
    const root: number = this.heap[0];
    // 마지막 값 추출
    const lastNode: number = this.heap.pop() as number;
    // pop 진행 후 배열 길이가 1 이상이라면
    if (this.heap.length !== 0) {
      // 마지막 노드를 최상단 노드로 이동
      this.heap[0] = lastNode;
      // Down 정렬 진행
      this.bubbleDown();
    }
    // root 값 반환 진행
    return root;
  }

  // 값 넣는 인덱스
  push(value: number): void {
    this.heap.push(value);
    this.bubbleUp();
  }

  //Down 정렬 진행
  bubbleDown(): void {
    let index = 0;
    const lastIndex = this.size() - 1;

    while (true) {
      let smallest = index;
      let leftChildIndex = this.getLeftChildIndex(index);
      let rightChildIndex = this.getRightChildIndex(index);
      if (
        (leftChildIndex < lastIndex &&
          this.heap[leftChildIndex] < this.heap[smallest]) ||
        (rightChildIndex < lastIndex &&
          this.heap[rightChildIndex] < this.heap[smallest])
      ) {
        if (
          this.heap[rightChildIndex] < this.heap[leftChildIndex] &&
          rightChildIndex < lastIndex
        ) {
          this.swap(rightChildIndex, smallest);
          smallest = rightChildIndex;
        } else {
          this.swap(leftChildIndex, smallest);
          smallest = leftChildIndex;
        }
      }
    }
  }

  // up 정렬 진행
  bubbleUp(): void {
    let childIndex = this.size() - 1;
    let parentIndex = this.getParentIndex(childIndex);
    while (this.heap[childIndex] < this.heap[parentIndex]) {
      this.swap(childIndex, parentIndex);
      childIndex = parentIndex;
      parentIndex = this.getParentIndex(childIndex);
    }
  }
}

Heap sort 알고리즘 특징

장점

• 시간 복잡도가 좋은편
• 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 이다.

Heap sort 의 시간복잡도

• 힙 트리의 전체 높이가 거의 log₂n(완전 이진 트리이므로)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 log₂n만큼 소요된다.
• 요소의 개수가 n개 이므로 전체적으로 O(nlog₂n)의 시간이 걸린다.
• T(n) = O(nlog₂n)

정렬 알고리즘 시간 복잡도

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

참조

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog