6.1 힙(Heap)이란?

• 완전 이진 트리의 형태의 자료구조
• 부모 자식 노드 간의 값을 비교하여 노드의 위치 결정
• 힙의 규칙: 부모 노드가 자식 노드보다 항상 크거나 같은 속성 유지
  • 루트 노드: 항상 최댓값 or 최솟값
  • 최댓값/최솟값 찾기 시간 복잡도: 배열 사용 = Ο(n) > 힙 사용 = O(logn)
• 우선순위 큐 구현에 가장 효율적인 자료구조

<aside> 💡 우선순위 큐(Priority Queue)란?

• 추상 자료형(Abstract Data Type) 중 하나로, 우선순위를 가진 데이터로 구성된 자료 자체의 형태와 연산들을 수학적으로 정의한 것입니다.
• 큐의 데이터는 먼저 추가된 데이터가 먼저 삭제되는 반면, 우선순위 큐의 데이터는 추가된 순서와 상관없이 우선순위가 높은 데이터가 먼저 삭제된다는 특징이 있습니다.
• 우선순위 큐는 배열, 연결 리스트, 힙 등 다양한 자료구조로 구현이 가능합니다. </aside>

6.2 힙(Heap) 활용 사례

• 운영체제 프로세스 대기열
• 힙 정렬
• 허프만 코드

6.3 힙(Heap)관련 용어 정리

그림 2-25 | 최대 힙

그림 2-26 | 최소 힙

• 최대 힙(Max Heap)

  • (완전 이진 트리)
  • (부모 노드 ≥ 자식 노드)
  • 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 완전 이진 트리

• 최소 힙(Min Heap)

  • (완전 이진 트리)
  • (부모 노드 ≤ 자식 노드)
  • 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 완전 이진 트리

6.4 힙(Heap)의 구현

• 최대 힙을 구현하기 위한 클래스 Heap 선언

  • 프로퍼티로 인덱스 0을 건너뛰고 1부터 시작하는 배열 nodes를 선언

    class Heap {
      constructor() {
        this.nodes = [null]; // nodes[0] = null;
      }
    ...
    

    <aside> 💡 왜 nodes[0]에는 null 값이 들어가나요?

    • 현재 노드를 기준으로 부모 노드를 찾을 때 현재 노드 / 2를 해줘야 하므로, 0부터 시작하는 경우, 부모 노드의 인덱스를 계산할 때마다 -1을 해줘야 하는 번거로움이 있기 때문입니다. </aside>

  • 삽입 메서드 선언

    • 인자로 들어온 값을 적절한 인덱스에 배치하기 위한 코드
      • 마지막 노드부터 루트 노드까지
      • 부모 노드와 현재 노드를 계속해서 비교
      • 현재 노드가 부모 노드보다 크다면 위치를 교환하는 작업을 반복

    ...
      insert(value) {
        // 가장 마지막 위치(가장 아래, 가장 오른쪽 노드)에 새로운 값이 추가
        this.nodes.push(value); 
        // 추가된 값의 위치, 마지막 인덱스부터 순회를 시작
        let crrIdx = this.nodes.length - 1;
        // 현재 노드의 인덱스를 crrIdx에, 부모 노드의 인덱스를 parIdx에 할당
        let parIdx = parseInt(crrIdx /2);
    
        // 현재 노드가 루트 노드가 아니고, 
    		// 부모 노드의 값이 현재 노드의 값보다 작다면
        while (crrIdx > 1 && this.nodes[parIdx] < this.nodes[crrIdx ]) { 
            
          // 현재 노드와 부모 노드의 값을 서로 교환
          [this.nodes[parIdx], this.nodes[crrIdx]] = [
          this.nodes[crrIdx],
          this.nodes[parIdx]
          ]; 
    
          // 순회를 계속하기 위해 crrIdx와 parIdx의 값 변경
          crrIdx= parIdx;
          parIdx = parseInt(crrIdx/2);
        }
      }
    ...
    

    

    그림 2-27 | 삽입 메서드의 작동 방식

    // 클래스 선언 이후에 실행합니다.
    // 삽입(insert) 메서드 예제 테스트
    let myHeap = new Heap();
    
    [90, 36, 17, 25, 26, 7, 1, 2, 3, 19].forEach(v=>{	myHeap.insert(v); })
    console.log(myHeap.nodes); 
    *// > (11) [null, 90, 36, 17, 25, 26, 7, 1, 2, 3, 19]*
    
    myHeap.insert(48); 
    console.log(myHeap.nodes); 
    *// > (12) [null, 90, 48, 17, 25, 36, 7, 1, 2, 3, 19, 26]*
    

  • 삭제 메서드 선언

    • 루트 노드를 제거하여 반환한 후 힙 속성 유지를 위한 노드 위치 정비 작업
      • 삽입 메서드와 반대로 동작
      • 루트 노드부터 마지막 노드까지
      • 현재 노드와 자식 노드를 계속해서 비교
      • 자식 노드가 현재 노드보다 크다면 위치를 교환하는 작업을 반복

    ...
    	remove() {
    	  let max = this.nodes[1]; // 루트 노드의 값을 max에 저장
    	
    	  if (this.nodes.length <= 2) {
          this.nodes = [null];
    	  } else { // 배열의 가장 마지막 값을 루트 노드 자리에
          this.nodes[1] = this.nodes.pop(); 
    	  }
    	
    	  // 루트 노드부터 시작하여 순회를 시작 (삽입과 반대)
    	  let crrIdx = 1; 
    	  let leftIdx = crrIdx * 2;
    	  let rightIdx = crrIdx * 2 + 1;
    	
    	  if (!this.nodes[leftIdx]) { 
          // 힙(Heap)은 완전 이진 트리 형태이므로, 
          // 자식 노드가 더 이상 존재하지 않는다는 의미
          return max;
    	  }
    	
    	  while ( // 자식 노드 중 하나라도 현재 노드보다 크다면
    	    this.nodes[leftIdx] > this.nodes[crrIdx] || 
    	    this.nodes[rightIdx] > this.nodes[crrIdx]
    	  ) { // 좌 우 자식 노드 중 더 큰 자식 노드nodes[maxIdx]와 
          let maxIdx =
          this.nodes[leftIdx] > this.nodes[rightIdx] ? leftIdx : rightIdx;
    
          // 현재 노드인 부모 노드 nodes[crrIdx]의 값을 교환
          [this.nodes[maxIdx], this.nodes[crrIdx]] = 
    				[this.nodes[crrIdx], this.nodes[maxIdx]]; 
    	
          // 순회를 계속하기 위해 crrIdx와 parIdx의 값을 변경
          crrIdx = maxIdx;
          leftIdx = crrIdx * 2;
          rightIdx = crrIdx * 2 + 1;
    	  }
    	  return max;
      }
    } // 클래스 선언 끝
    

    

    그림 2-28 | 삭제 메서드 작동 방식

    // 클래스 선언 이후에 실행합니다.
    // 삭제(remove) 메서드 예제 테스트
    let myHeap2 = new Heap();
    
    [90, 36, 17, 25, 26, 7, 1, 2, 3, 19].forEach(v=>{	myHeap2.insert(v); })
    console.log(myHeap2.nodes); 
    *// > (11) [null, 90, 36, 17, 25, 26, 7, 1, 2, 3, 19]*
    
    console.log(myHeap2.remove()); *// > 90*
    console.log(myHeap2.nodes); *// > (10) [null, 36, 26, 17, 25, 19, 7, 1, 2, 3]*
    

    • 힙 객체를 활용한 힙 정렬

    // + 힙정렬
    let myHeap3 = new Heap();
    
    [90, 36, 17, 25, 26, 7, 1, 2, 3, 19].forEach(v=>{ myHeap3.insert(v); })
    console.log(myHeap3.nodes); // > (11) [null, 90, 36, 17, 25, 26, 7, 1, 2, 3, 19]
    
    let heapSort = [];
    let heap3Length = myHeap3.nodes.length - 1; // null을 제외한 길이
    for(let i = 0; i < heap3Length; i++){
      heapSort.push( myHeap3.remove());
    }
    console.log('힙정렬: ', heapSort);
    *// > (10) [90, 36, 26, 25, 19, 17, 7, 3, 2, 1]*