[115일차]힙 자료구조

힙 자료구조

힙은 우선순위 큐를 위해서 만들어진 특별한 자료구조다.
이진 탐색트리와 유사한 모양을 가지고 있는데, 힙은 중복된 값을 허용하지 않는다.
또, 힙은 완전 오름차순 형태로 정렬된게 아닌 불완전 정렬상태 이다.
우선순위 큐의 활용 사례로는,

• 게임엔진에서 각 액터의 우선순위를 정한다.
• 서버에서 많은 트래픽을 처리 할 때 우선처리해야할 트래픽을 정한다.

다른 활용도 있는데, 이건 내가 문제를 풀거나 해봐야 할것같다.
힙으로 우선순위큐를 구현하는 이유는 나중에 들어온 값이라도 우선순위를 줄 수 있기 때문이다.

---

힙자료구조의 중점은,

• 왼쪽 노드부터 삽입하고 값에 따라 부모자식 관계가 바뀌지 좌우가 바뀌지않는다.
• 자식노드는 부모보다 최대힙(큰거우선)일때 같거나 작으면되고,
• 최소힙(작은거우선)일때 크거나 같으면 된다.
• 완전 이진트리 상태이다.

저러한 형태의 힙을 그림으로 그려보면,

0번째 인덱스는 구현 편의상 비운다.
완전 이진트리 상태이며,
왼쪽부터 값을 채우지만 내가 지금 그린 형태는, 최소힙(min heap) 이다.

여기서 알 수있는건,
왼쪽자식인덱스:(자기자신의 인덱스 * 2) 이고
오른쪽자식인덱스:(자기자신의 인덱스 * 2) + 1 이며
부모인덱스:parseInt(자기자신의 인덱스 / 2) 이다.

앞으로의 예제는 최소힙을 기준으로 하겠다.

---

요소 삽입

이전 이미지로 작업을 하려다가 날아갔다..

최소힙에서 새로운 요소를 삽입할 때 일어나는 과정을 살펴보자

요소 -1 을 삽입해보자
요소하나는 우선 맨끝 인덱스로 삽입이 된다.

저 상태는 분명히 최소힙 상태가 아니다.
자식인 -1이 2보다 작기 때문이다.

그래서 자신의 상단인 2와 자리를 바꾼다.
밑에 배열도 주목해서보자.

여전히 -1은 자신의 상단보다작다.
그래서 1과 자리를 바꾼다.

요롷게 위계질서가 잡힐때까지 정리가되면
삽입은 끝나게된다.

---

요소삭제

힙에서 삭제는 흔히들 아는 그래프에서 특정 노드를 찾아서,
그 노드를 삭제하고 나오는게 아니라
최소힙에서는 요소중 최소값에해당 하는 요소를
최대힙에서는 요소중 최대값에해당 하는 요소를
삭제하는 것이다.
1번째 인덱스를 삭제하는것인데, 디큐와 똑같아보이지만, 다르다.
디큐는 맨 앞에있는 요소를 그냥 삭제하면 그만이지만,
우선순위가있는 힙에서 디큐는 삭제를 한 후 순서까지 다시 맞춰줘야 한다.

위 -1을 넣은 힙에서 맨 앞 요소를 삭제해보겠다.

일단은 이런 혼돈이 초래하고 만다.
그렇다고 무작정 배열을 한칸씩 앞땡기면
모습이 어떻게될지 상상은 각자몫이다.

우선은 맨 마지막 자식인 2를 땜빵시켜준다.

자식들과 자기자신을 비교해서,
자신보다 더 작은 자식이 있으면 자리를 바꿔준다.

---

최소힙 자바스크립트 코드

class minHeap {
  constructor (){
    // 요소들을 나타낸다
    this.elements = [,];
  }
  //요소삽입 메소드
  insert(el) {
    //우선 맨 마지막 요소에 추가할 엘리먼트를 추가한다.
    //swap함수 선언(추가한 값의 인덱스)
      //idx가 0이면 함수종료
      //요소와 부모인덱스의 자리를 바꾼다.  
      //idx = ~~(idx / 2)
        //자신의 부모인덱스값이 자신의값보다 크거나 같을 때 스왑
    const {elements} = this;
    elements.push(el);
    const index = elements.length - 1;
    //바꾸는 함수
    function swap(idx){
      if(idx === 0)return;
      [elements[idx], elements[~~(idx / 2)]] = [elements[~~(idx / 2)], elements[idx]];
      idx = ~~(idx / 2);
      if(elements[idx] <= elements[~~(idx / 2)])swap(idx);
    }
    if(elements[index] <= elements[~~(index / 2)])swap(index);
  }
  //삭제 메소드
  delete() {
    //우선 맨앞요소와 맨뒷자리애랑 바꾼다.
    //맨뒤로간 맨 앞요소를 삭제한다.
    //swap함수 선언 (바꿀인덱스, 바꿔질인덱스)
      //바꿀인덱스와 바꿔질인덱스를 교체한다.
      //해당인덱스가 자식을 가지고있을때
        //왼쪽자식과 비교해서 해당인덱스값이 더 크면
          //자리교체
        //오른쪽자식과 비교해서 해당인덱스값이 더 크면
          //자리교체
    const {elements} = this;
    const backmost = elements.length - 1;
    [elements[1], elements[backmost]] = 
    [elements[backmost], elements[1]];
    elements.pop();
 
    function swap (change, changed){
      [elements[change], elements[changed]] = 
      [elements[changed], elements[change]];
      change = changed;
      const leftChildIdx = change * 2;
      const rightChildIdx = change * 2 + 1;
      if(elements[leftChildIdx]){
        if(elements[leftChildIdx] < elements[change]){
          swap(change, leftChildIdx);
        }
        if(elements[rightChildIdx] < elements[change]){
          swap(change, rightChildIdx);
        }
      }
    }
 
    if(elements[1] > elements[2]) swap(1, 2);
    if(elements[1] > elements[3]) swap(1, 3);
  }
}
/* test */
const heap = new minHeap();
heap.insert(1);
heap.insert(3);
heap.insert(2);
heap.insert(6);
heap.insert(9);
console.log(heap.elements);
heap.insert(-1);
console.log(heap.elements);
heap.delete();
console.log(heap.elements);
heap.delete();
console.log(heap.elements);
heap.delete();
console.log(heap.elements);
heap.insert(1);
console.log(heap.elements);
heap.insert(11);
heap.insert(4);
heap.insert(2);
console.log(heap.elements);
heap.delete();
console.log(heap.elements);

테스트 결과

---