힙 정렬(Heap Sort)

힙(Heap)

• 가장 높은 항목이나 가장 낮은 항목을 O(1)시간에 반환할 수 있는 자료구조 입니다.
• Tree 형식과 비슷하고 포인터가 아닌 배열을 기반으로 한 완전 이진 트리입니다.
• Tree와 다르게 중복된 값도 추가를 할 수 있습니다.
• 우선 순위 큐 개념을 이용하여 데이터들이 우선순위를 가지고 있고 빠져 나갈때 우선순위로 빠져나갑니다.

힙 종류

최대 힙(Max-Heap)

• 최상위 노드가 가장 높은 값을 갖고 있습니다.
• 부모 노드 값 >= 자식 노드의 값

최소 힙(Min-Heap)

• 최상의 노드가 가장 낮은 값을 갖고 있습니다.
• 부모 노드 값 <= 자식 노드 값

힙 배열 인덱스 구조

• 노드 : 인덱스
• 자신 : N
• 부모 : (N-1)/2
• 왼쪽 자식 : (N*2)+1
• 오른쪽 자식 : (N*2)+2

(1) index - 자신
(2) index*2 + 1; - 왼쪽 자식
(3) index*2 + 2; - 오른쪽 자식

  (1)(2)(3)
!! 0,1,2
!! 1,3,4
!! 2,5,6
!! 3,7,8
!! 4,9,10
                 0
       1                   2
    3     4           5      6
 7   8  9  10   11 12 13 14      

힙 정렬(Heap Sort)

• 완전 이진 트리를 형식으로 만들어진 힙 자료구조를 정렬하는 알고리즘입니다.
• 불안정 정렬에 속합니다.
• 오름차순, 내림차순 정렬이 있습니다.

사용 예시

• 가장 크거나 작은 값을 구할 때
• 최대 i 만큼 떨어진 요소들을 정렬할 때

장점

• 최악의 경우에도 빠른 시간 복잡도를 보장합니다.
• 가장 크거나 작은 값을 필요로 할 때 유용합니다.

단점

• 데이터들의 상태에 따라 다른 정렬들에 비해서 조금 느린편입니다.
• 데이터의 순서가 바뀌는 불안정한 알고리즘입니다.

code

// ----------------------- 힙 클래스 -----------------------

function heap() {
  this.items = [];
}

heap.prototype.swap = function(index1, index2) {
  var temp = this.items[index1];
  this.items[index1] = this.items[index2];
  this.items[index2] = temp;
}

heap.prototype.parentIndex = function(index) {
  return Math.floor((index-1)/2);
}

heap.prototype.leftChildIndex = function(index) {
  return index*2+1
}

heap.prototype.rightChildIndex = function(index) {
  return index*2+2
}

heap.prototype.parent = function(index) {
  return this.items[this.parentIndex(index)];
}


heap.prototype.leftChild = function(index) {
  return this.items[this.leftChildIndex(index)];
}

heap.prototype.rightChild = function(index) {
  return this.items[this.rightChildIndex(index)];
}


// ----------------------- 삼투 구현 -----------------------

function minHeap() {
  this.items = [];
}
minHeap.prototype = Object.create(heap.prototype);


minHeap.prototype.bubbleDown = function() {
  var index = 0;

  while(this.leftChild(index) && (this.leftChild(index) < this.items[index] ||
        this.rightChild(index) < this.items[index]) ) {
          var smallerIndex = this.leftChildIndex(index);
          if(this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
            smallerIndex = this.rightChildIndex(index);
          }
          this.swap(smallerIndex, index);
          index = smallerIndex;
        }
}

minHeap.prototype.bubbleUp = function() {
  var index = this.items.length-1;
  while(this.parent(index) && this.parent(index) > this.items[index]) {
    this.swap(this.parentIndex(index), index);
    index = this.parentIndex(index);
  }
}


// ----------------------- 최소 힙 -----------------------


minHeap.prototype.add = function(item) {
  this.items[this.items.length] = item;
  this.bubbleUp()
}

minHeap.prototype.poll = function() {
  var temp = this.items[0];
  this.items[0] = this.items[this.items.length-1];
  this.items.pop();
  this.bubbleDown();
  return temp;
}


var minH = new minHeap();
minH.add(1);
minH.add(10);
minH.add(5);
minH.add(100);
minH.add(8);
console.log(minH)

console.log(minH.poll());
console.log(minH.poll());
console.log(minH.poll());
console.log(minH.poll());
console.log(minH.poll());
console.log(minH)

 

설명

// ----------------------- 힙 클래스 -----------------------

// 배열을 기반으로 한 완전 이진 트리이기 때문에 배열로 초기화함
function heap() {
  this.items = [];
}

// 값 비교 후 위치를 바꿔야할때 실행 되는 함수
heap.prototype.swap = function(index1, index2) {
  var temp = this.items[index1];
  this.items[index1] = this.items[index2];
  this.items[index2] = temp;
}

// 해당 index의 부모 인덱스 찾는 함수
heap.prototype.parentIndex = function(index) {
  return Math.floor((index-1)/2);
}

// 해당 index의 왼쪽 자식 인덱스 찾는 함수
heap.prototype.leftChildIndex = function(index) {
  return index*2+1
}

// 해당 index의 오른쪽 자식 인덱스 찾는 함수
heap.prototype.rightChildIndex = function(index) {
  return index*2+2
}




// 1. 해당 인덱스의 부모 인덱스를 찾는다
// 2. this.items[부모 인덱스]를 통해 값을 찾는다

// 해당 index의 부모 값을 찾는 함수
heap.prototype.parent = function(index) {
  return this.items[this.parentIndex(index)];
}

// 해당 index의 왼쪽 자식 값을 찾는 함수
heap.prototype.leftChild = function(index) {
  return this.items[this.leftChildIndex(index)];
}

// 해당 index의 오른쪽 자식 값을 찾는 함수
heap.prototype.rightChild = function(index) {
  return this.items[this.rightChildIndex(index)];
}





// ----------------------- 삼투 구현 -----------------------

function minHeap() {
  this.items = [];
}

// 프로토타입을 복사 해서 힙 클래스로부터 도움 함수를 상속받는다
minHeap.prototype = Object.create(heap.prototype);



// bubbleDown함수는 poll함수에서 트리의 가장 밑부분(배열의 마지막 요소)을 꼭대기(배열[0])에 저장했지만 최솟값인지 알수 없기 때문에
// 반복문을 통해 해당 값 위치를 찾아주는 로직이다.

// (1) - index에 0을 저장해 트리의 꼭대기부터 내려가도록 한다.
// while
// (2) - while문 조건에서 (왼쪽 자식의 존재 여부), (현재 값(부모) > 왼쪽 자식 && 현재 값(부모) > 오른쪽 자식)를 확인한다.
// (3) - (2)조건문을 통과한다면 smallerIndex에 왼쪽 자식 인덱스 값을 임시로 저장한다.
// (4) - 왼쪽 자식과 오른쪽 자식의 값을 비교하고 더 값이 작은 쪽에 index를 smallerIndex에 저장한다.
// (5) - (1)의 인덱스(index)와 (4)의 인덱스(smallerIndex에) 위치를 바꿔준다(위치가 바뀐다는 의미는 트리의 꼭대기에서 점점 내려온다는 의미)
// (6) - index의 값을 변경하면서 자신의 자리를 찾아간다.
minHeap.prototype.bubbleDown = function() {
  var index = 0; // (1)
  while(this.leftChild(index) && (this.leftChild(index) < this.items[index] || // (2)
        this.rightChild(index) < this.items[index]) ) {
          var smallerIndex = this.leftChildIndex(index); // (3)
          if(this.rightChild(index) && this.rightChild(index) < this.items[smallerIndex]) {
            smallerIndex = this.rightChildIndex(index); // (4)
          }
          this.swap(smallerIndex, index); // (5)
          index = smallerIndex; // (6)
        }
}




// bubbleUp함수는 트리모양에서 가장 밑부분에서 꼭대기까지 조건에 맞다면 올라오는 로직이다.

// (1) - index에 add함수에서 추가한 요소의 위치(this.items.length-1)값을 넣는다.
// (2) - while문 조건에서 부모의 존재 여부와 부모의 값 > 현재 추가한 값 일때 swap함수를 이용해 교체한다.
// (3) - swap과정에서 위치를 바꾸고 index값을 바꿈으로써 현재 추가한 값의 위치를 (2)조건문과 비교하여 찾아간다.
//     !!! 현재 추가한 값이 최솟값이라면 가장 밑부분에서 꼭대기까지 swap을 하게 된다.
minHeap.prototype.bubbleUp = function() {
  console.log('bubbleUp 함수 실행')
  var index = this.items.length-1; // (1)
  console.log(`방금 추가한 값 : ${this.items[index]}, 부모의 값 : ${this.parent(index)}`)
  console.log('')
  // 부모값이 현재 추가한 값보다 큰 경우 스왑하는 반복문
  while(this.parent(index) && this.parent(index) > this.items[index]) { // (2)
    this.swap(this.parentIndex(index), index);
    index = this.parentIndex(index); // (3)
  }
}







// ----------------------- 최소 힙 -----------------------


// 배열의 총 길이에 +1 위치에 해당 item 값을 추가하고 bubbleUp()함수 실행한다
// 즉 배열의 크기가 0부터 추가횟수만큼 증가한다는 의미!!
minHeap.prototype.add = function(item) {
  this.items[this.items.length] = item;
  this.bubbleUp()
}


// 최소 값을 꺼내지만 배열에서 제거 할때는 가장 마지막 노드를 제거한다.
// 즉 var a = [1,2,3,4,5]에서 1을 제거하지만 a.pop()을 통해 배열의 마지막 요소를 삭제함

// 이유
// (1) temp 임시 변수에 최솟값(arr[0])을 저장한다.
// (2) arr[0]번째에 arr[마지막 인덱스] 값을 저장한다.
// (3) arr.pop()을 통해 마지막 인덱스를 제거한다(하지만 0번째 index에 저장되어있으므로 상관없다)
// (4) bubbleDown()함수를 실행한다. => 그 이유는 arr[0]번째에 arr[마지막 인덱스] 값을 저장했지만 최솟값인지 모르기 때문에
// (5) 최솟값(temp)을 return하여 출력한다.
minHeap.prototype.poll = function() {
  var temp = this.items[0]; // (1)
  this.items[0] = this.items[this.items.length-1]; // (2)
  this.items.pop(); // (3)
  this.bubbleDown(); // (4)
  return temp; // (5)
}






var minH = new minHeap();
minH.add(10);
minH.add(3);
minH.add(8);
minH.add(5);
minH.add(100);
minH.add(1);
// bubbleUp 함수 실행
// 방금 추가한 값 : 10, 부모의 값 : undefined
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 3, 부모의 값 : 10
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 8, 부모의 값 : 3
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 5, 부모의 값 : 10
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 100, 부모의 값 : 5
//
// bubbleUp 함수 실행
// 방금 추가한 값 : 1, 부모의 값 : 8

console.log(minH) // heap { items: [ 1, 5, 3, 10, 100, 8 ] }

console.log(minH.poll()); // 1
console.log(minH.poll()); // 3
console.log(minH.poll()); // 5
console.log(minH.poll()); // 8
console.log(minH.poll()); // 10

console.log(minH) // heap { items: [ 100 ] }