[ 비선형 자료구조 ] heapify & heap sort

heapify와 heap sort

  힙은 모든 부모 노드가 자식 노드 이상(max-heap) 혹은 이하(min-heap)의 값을 가지는 완전이진트리이며, 주어진 배열이나 리스트를 힙 구조로 만드는 연산이 heapify입니다. heap sort는 정렬되지 않은 배열이나 리스트를 heapify 프로세스를 이용해 heap 자료구조로 변환한 뒤 root 노드의 값을 추출해 배열 혹은 리스트에 추가하는 과정을 모든 요소가 정렬될때까지 반복하는 알고리즘 입니다.

 

• heapify : 배열이나 리스트를 힙 구조로 재구성하는 연산
• heap sort : 힙에서 root값을 반복적으로 추출해 정렬된 배열을 만드는 알고리즘

 

heapify

  heapify는 배열을 인자로 받아 힙의 특성에 맞게 재구성시키는 연산입니다. 이러한 heapify는 top-down / O(nlogn), bottom-up / O(n) 이 두 가지의 방식으로 이루어질 수 있으며, 일반적으로 보다 효율적인 bottom-up 방식이 사용됩니다. top-down 방식은 빈 힙에 원소를 차례로 삽입해 가며 아래로 확장해 가는 방식이며, 매 삽입 시 가장 마지막 자리에 삽입된 노드가 부모노드와 비교하며 sift-up됩니다. bottom-up 방식의 경우 주어진 배열을 완성되지 않은 힙이라 가정하고 리프노드가 아닌 가장 마지막 노드(힙의 길이 / / 2 번째 노드) 부터 한단계씩 올라가며 값을 비교하고 필요시 sift-down하며 힙을 완성하는 방식입니다. 이 글에서는 bottom-up 방식에 대해 다루겠습니다.

 

  아래 코드는 부모노드와 두 자식노드로 구성된 서브트리의 크기를 비교하고, 교환하여 max-heap의 특성을 맞게합니다. 만약 교환이 이루어 질 경우(자식 노드의 크기가 큰 경우) heapify는 해당 자식노드를 루트노드로 간주하여 재귀적 호출되며, 이를 통해 교환이 이루어진노드를 따라가며 대해 트리상에서 정렬됩니다. 

 

function heapify(arr, lenArr, rootIdx) {
  let largestIdx = rootIdx;
  let leftChildIdx = 2 * rootIdx + 1;
  let rightChildIdx = 2 * rootIdx + 2;

  if (leftChildIdx < lenArr && arr[leftChildIdx] > arr[rootIdx]) {
    largestIdx = leftChildIdx;
  }

  if (rightChildIdx < lenArr && arr[rightChildIdx] > arr[largestIdx]) {
    largestIdx = rightChildIdx;
  }

  if (largestIdx != rootIdx) {
    [arr[rootIdx], arr[largestIdx]] = [arr[largestIdx], arr[rootIdx]];

    heapify(arr, lenArr, largestIdx);
  }
}

 

  

heapify를 이용한 heap sort (Javascript)

  아래 코드는 두 반복문을 통해 작동합니다. 각각의 역할은 아래와 같습니다.

1. bottom-up 방식의 heapify를 통해 주어진 arr를 max-heap으로 재구성
2. root 노드의 값과 i 인덱스의 값을 교환한 후 i를 제외한 나머지 배열을 heapify를 통해 다시 힙의 성질에 맞게 재정렬 한다. i는 마지막 인덱스에서 부터 root까지 차례로 바뀌며 결과적으로 배열을 오름차순으로 정렬하게 된다.

function heapify(arr, lenArr, rootIdx) {
  let largestIdx = rootIdx;
  let leftChildIdx = 2 * rootIdx + 1;
  let rightChildIdx = 2 * rootIdx + 2;

  if (leftChildIdx < lenArr && arr[leftChildIdx] > arr[rootIdx]) {
    largestIdx = leftChildIdx;
  }

  if (rightChildIdx < lenArr && arr[rightChildIdx] > arr[largestIdx]) {
    largestIdx = rightChildIdx;
  }

  if (largestIdx != rootIdx) {
    [arr[rootIdx], arr[largestIdx]] = [arr[largestIdx], arr[rootIdx]];

    heapify(arr, lenArr, largestIdx);
  }
}

function heapSort(arr) {
	let nonLeafIdx = Math.floor(arr.length / 2) - 1
    
    for (let root = nonLeafIdx; root >= 0; root--) {
    	heapify(arr, arr.length, root);
    }
    
   	for (let i = arr.length - 1; i > 0; i--) {
    	[arr[i], arr[0]] = [arr[0], arr[i]];
        heapify(arr, i, 0)
    }
}