1. 개념

• 이진 힙은 Complete binary tree (왼쪽부터 꽉꽉 채워가는 )
  
  
• 완전이진트리 특징으로는, 배열로 전환 가능하다는 것 (왼쪽부터 채워가기 때문에)
  
  
• 굳이 트리로 표현할 필요 없이 편하게 배열로 표현 ⇒ cuz it’s already Complete Binary Tree => (ex) [0, 1, 2, 3, 4]
  
  
• 최대힙과 최소힙으로 두 개가 있다

---

인덱스 공식

왼쪽 자식 인덱스 = 해당 인덱스 * 2 + 1

오른쪽 자식 인덱스 = 해당 인덱스 * 2 + 2

부모 인덱스 = Math.floor( ( i - 1 ) / 2 )

---

이진탐색트리 vs 최대힙 vs 최소힙

힙은 숫자 세트가 있을 때 다양한 조합이 나올 수 있음

WHY ? 서브트리 바뀌어도 힙 유지

반면, BST는 트리 모양이 고정일 시 경우의 수 1가지

• BST ⇒ 왼쪽 small, 오른쪽 big
• 최대힙 ⇒ 위쪽 big, 아래쪽 small (부모 > 자식)
• 최소힙 ⇒ 위쪽 small, 아래쪽 big (자식 > 부모)

---

시간복잡도

특정값 삭제/수정 시 heapify 과정 필요

cf. 공간복잡도는 사실상 배열이니 O(n)…

(1) 조회 O(n)

사실상 배열이기 때문에 index 0 부터 length까지 조회하는 것

(2) 삽입과 삭제 O(logN)

= 힙이면 새로운 값을 넣어도 최대힙이면 always 최대힙, 최소힙이면 최소힙으로 유지됨

• 삭제는 항상 root 노드만
• 왜? 특정값을 삭제할 시, 빈 자리를 노드가 채워줘야 하므로 heapify와 다를 바 없음ㅠㅠ

즉, root를 제거했을 때도 힙이 유지되게끔 알고리즘 짜야

(3) 힙 정렬 O(nlogN)

힙은 “정렬” 목적으로 자주 쓰임 (훌륭한 정렬 알고리즘)

• 힙에서는 삭제를 length 만큼 하면 자동으로 “정렬”됨
  -- 최대힙 (내림차순), 최소힙(오름차순)

(4) 수정 Heapify O(n)

특정값을 수정하거나 삭제했을 때 내부적으로 쓰이는 함수

1단계. 선 조회 O(n)

2단계. (힙이 깨졌을 때) 힙이 아닌 Tree를 힙으로 바꾸는 과정 필요

cf. 수정이 아니더라도 BST를 힙으로 바꾸고 싶을 때도 we call it “Heapify”

시간복잡도 동일하게 O(n)

---

2. 구현하기

(1) insert 구현

class Heap { // 최대힙
    arr = [];

    #reheapUp(index){
        if(index > 0){ // 루트가 아니면
            const parentIndex = Math.floor((index - 1) / 2);
            if(this.arr[index] > this.arr[parentIndex]){ // 부모보다 클 때
                // 값(자리) 바꾸기
                const temp = this.arr[index];
                this.arr[index] = this.arr[parentIndex];
                this.arr[parentIndex] = temp;
                this.#reheapUp(parentIndex); // 부모자리에서 다시 재귀함수 호출
            }
        }        
    }
    insert(value){ // O(logN) 이런 애들은 보통 재귀 사용, 부모랑 비교해서 바꾼다
        const index = this.arr.length; // 배열의 마지막에 값 insert 하고
        this.arr[index] = value;
        this.#reheapUp(index);
    }
}

실행결과

const heap = new Heap();
heap.insert(8);
heap.insert(19);
heap.insert(23);
heap.insert(32);
heap.insert(45);
heap.insert(56);
heap.insert(78);
heap;

---

(2) remove 구현

class Heap { // 최대힙
    arr = [];

	#reheapDown(index){
        const leftIndex = index * 2 + 1;
        if(leftIndex < this.arr.length){ // 자식이 없을 때까지
            const rightIndex = index * 2 + 2;
            const bigger = this.arr[leftIndex] > this.arr[rightIndex] ? leftIndex : rightIndex;
            if(this.arr[index] < this.arr[bigger]){ // 본인이 자식보다 작을 경우
                const temp = this.arr[index];
                this.arr[index] = this.arr[bigger];
                this.arr[bigger] = temp;
                this.#reheapDown(bigger);
            }
        }
    }
    remove(){ // root만 삭제 
        if(this.arr.length === 0){ // 힙이 비어있는 경우
            return false;
        }
        if(this.arr.length === 1){
            return this.arr.pop();
        }
        const root = this.arr[0];
        this.arr[0] = this.arr.pop(); // 마지막 거 뽑아서 무한하게 재귀적으로 비교
        this.#reheapDown(0);
        return root;
    }
}

실행결과

heap.remove();
heap.remove();
heap.remove();
heap.remove();
heap.remove();
heap.remove();
heap.remove();

---

(3) sort(힙 정렬) 구현

class Heap { // 최대힙
    arr = [];

	sort(){ // 힙 정렬
        const sortedArray = [];
        while(this.arr.length > 0){ // length 만큼 remove로 push하기
            sortedArray.push(this.remove());
        }
        return sortedArray;
    }
}

실행결과

heap.insert(8);
heap.insert(19);
heap.insert(23);
heap.insert(32);
heap.insert(45);
heap.insert(56);
heap.insert(78);
console.log(heap.sort());

---

(4) heapify 구현

[1] update의 경우

class Heap { // 최대힙
    arr = [];
	
    update(value, newValue){ // 특정값
      const index = this.search(value);
      if( index === null){
        return false;
      } 
      this.arr[index] = newValue;
      for(let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--){ //O(1/2 N)
        this.#heapify(i); // leaf 가 아닌 노드부터 루트까지, O(1)
        // 시간복잡도 1 * O(1/2N) => O(N)인 이유는, 계수(1/2)는 무시하기 때문
      }
      
	#heapify(index){ // 마지막에서 세었을 때 leaf가 아닌 첫번째 노드부터 시작, 자식과 비교해서 바꿔주기 반복
        // 끝에서 leaf부터 1번째 노드 찾는 공식 
        // Math.floor(( length / 2 ) - 1)
        const leftIndex = index * 2 + 1;
        const rightIndex = index * 2 + 2;
        const bigger = (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0) ? leftIndex : rightIndex;
        if(this.arr[index] < this.arr[bigger]){ // 본인이 자식보다 작을 경우 "자식"이 최대힙이니 바꿔주기
            const temp = this.arr[index];
            this.arr[index] = this.arr[bigger];
            this.arr[bigger] = temp;
            this.#reheapDown(bigger);
        }
    }
}

실행결과

heap.update(23, 90);
heap;

[2] removeValue의 경우

class Heap { // 최대힙
    arr = [];

	removeValue(value){ // 루트 삭제가 아니라 "특정값" 삭제
        const index = this.search(value);
        if( index === null){
            return false;
        } 
        this.arr.splice(index, 1); // 인덱스를 없애버림
        for(let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--){ 
            this.#heapify(i); // 그리고 다시 heapify 돌려버리기
        }   
    }

    #heapify(index){ // 마지막에서 세었을 때 leaf가 아닌 첫번째 노드부터 시작, 자식과 비교해서 바꿔주기 반복
        // 끝에서 leaf부터 1번째 노드 찾는 공식 
        // Math.floor(( length / 2 ) - 1)
        const leftIndex = index * 2 + 1;
        const rightIndex = index * 2 + 2;
        const bigger = (this.arr[leftIndex] || 0) > (this.arr[rightIndex] || 0) ? leftIndex : rightIndex;
        if(this.arr[index] < this.arr[bigger]){ // 본인이 자식보다 작을 경우 "자식"이 최대힙이니 바꿔주기
            const temp = this.arr[index];
            this.arr[index] = this.arr[bigger];
            this.arr[bigger] = temp;
            this.#reheapDown(bigger);
        }
    }
}

실행결과

heap.removeValue(32);
heap;