힙 (Heap) & Max heap 구현 (javascript)

힙(Heap) 기본개념

Binary Tree (이진 트리)

• 한 노드가 최대 두개의 노드를 자식으로 가질 수 있는 트리 구조
• 마지막 레벨을 제외한 모든 레벨에는 노드들이 가득 차있고, 마지막 레벨의 노드들고 좌측부터 순서대로 들어가 있음
• 노드 개수를 알면, 트리의 구조를 특정할 수 있다.

현재 노드 번호 i

• 현재 노드 parent node의 번호 = (i - 1) / 2
• 현재 노드의 left child node의 번호 = i * 2 + 1
• 현재 노드의 right child node의 번호 = i * 2 + 2
  
  
  -> 1차원 배열로 이진트리를 나타내기 용이하다.
  

Heap (힙)

• 완전 이진 트리로 구현된 자료구조
  • 연산을 빠르게 하기 위해 완전 이진 트리 사용
• 부모노드의 키 값과 자식 노드의 키 값 사이에 대소관계가 성립합
  • Max heap, Min heap 존재
  • 느슨한 정렬상태 (반정렬 상태) 유지
• 중복값 허용, 최댓값 최솟값을 쉽게 뽑기 위한 자료구조

Map heap (최대 힙)

• 부모 키 값이 자식노드 키 값보다 큰 힙
• Key (parent) >= Key (child)
• 가장 큰 값이 루트 노드에 존재

Min heap (최소 힙)

• 부모 키 값이 자식노드 키 값보다 작은 힙
• Key (parent) <= Key (child)
• 가장 작은 값이 루트 노드에 존재

Heap 사용 사례

• 우선순위 큐 (Priority Queue)
• Dijkstra 알고리즘
• 힙 정렬

---

Heap 구현

최대힙, 최소힙은 값의 비교 연산자만 다르고 나머지는 똑같기 때문에 최소힙은 생략함

배열로 나타낸 힙

• 힙은 트리를 배열로 나타낼 수 있다.

주어진 배열 = [10, 15, 30, 40, 50, 100, 40]
현재노드 Index = 6
부모노드 Index: Math.floor((자식노드 index - 1) / 2) = 2
왼쪽 자식 노드 Index = (부모노드 2) + 1 = 5
오른쪽 자식 노드 Index = (부모노드 2) + 2 = 6

기본 셋팅

// 부모노드 인덱스
getParentIndex(i) {
  return Math.floor((i - 1) / 2);
}

// 왼쪽 자식노드 인덱스
getLeftChildIndex(i) {
  return i * 2 + 1;
}

// 오른쪽 자식노드 인덱스
getRightChildIndex(i) {
  return i * 2 + 2;
}

삽입 알고리즘

1. 원소를 맨 마지막에 넣는다 push()
2. 부모의 노드와 비교해서 더 크다면 자리를 바꾼다 swap()
3. 현재 노드가 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2의 과정을 반복한다 heapiftUp()

추출 알고리즘

1. 배열의 최상위 노드를 꺼낸다 maxValue
2. 루트노드와 맨 끝에 있는 원소를 교체한다 this.data[0] = this.data[this.data.length - 1];
3. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다. this.data.length--;
4. 변경된 노드와 자식 노드를 비교한다. left, right index로 두 자식 간 노드의 크기를 비교하며 루트 노드보다 더 클 경우, 자리를 바꿔준다 heapifyDown(), swap()
5. 자식 노드 둘 보다 부모노드가 크거나 가장 바닥에 도달하지 않을 때까지 4번의 과정을 반복한다 heapifyDown()
6. 2에서 제거한 원래 루트 노드를 반환한다 poll(), return maxValue

Javascript로 Heap 구현

*️⃣ 기본 골격

• 부모의 Index, 자식 Index를 left와 right로 구분한다.
• 노드끼리 비교 후, index를 서로 바꿔주는 swap() 메소드를 만든다.

class Heap {
  constructor() {
    this.data = [];
  }

  // 기본 셋팅
  getParentIndex(i) {
    return Math.floor(i - 1 / 2);
  }

  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  swap(i1, i2) {
    const temp = this.data[i1];
    this.data[i1] = this.data[i2];
    this.data[i2] = temp;
  }

}

*️⃣ push

1. 원소를 맨 마지막에 넣는다 push()
2. 부모의 노드와 비교해서 더 크다면 자리를 바꾼다 swap()
3. 현재 노드가 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2의 과정을 반복한다 heapiftUp()

class Heap {
 ...
  // push 배열 끝에 넣기
  push(key) {
   this.data[this.data.length] = key;
   // 가장 큰 값일 수 있다. heap요구사항에 따라 자리를 바꿔줘야함 > hepifyUp()통해서 이뤄진다.
   this.heapifyUp();
  }
}

*️⃣ heapifyUp()

• Max heap에 맞게 가장 큰 노드는 트리의 최상단, 배열의 첫 번째 값으로 해주기 위해 방금 들어온 노드의 위치를 변수로 둔다.

1. currentIndex : 최근에 삽입된 노드의 Index
2. while문 : currentIndex의 요소가 상위요소보다 클 때까지 돌린다. 현재 요소 ( 가장 마지막, 밑에있던 요소)와 부모 요소의 값을 비교한다. 현재 요소가 크면 위로 올려야 하기 때문에 swap()을 쓴다. 
3. 비교를 거친후 새 위치에 대해 이를 반복해야 하므로 currentIndex를 비교했던 부모 요소의 Index로 재할당시 킨다. 

heapifyUp() {
    let currentIndex = this.data.length - 1;

    // current요소가 상위요소보다 클 때까지 돌린다.
    // 현재 요소 (가장마지막, 밑에있던 요소) 와 부모 요소의 값을 비교 한다. 
    // 현재요소가 크면 위로 올려야하기 때문에 swap()을 쓴다.
    while (
      this.data[currentIndex] > this.data[this.getParentIndex(currentIndex)]
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));

      // currentIndex를 비교했던 부모요소로 재할당시킨다.
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

*️⃣ poll() 추출

• 최대값을 추출하는 방법이다.
• heap 규칙을 지키기 위한 heapifyDown() 함수가 중요하다.

1. currendIndex : 최상위 노드를 지정한다.
2. while문 : 최상위에 있는 현재 노드보다 자식 노드가 더 크면 현재 노드와 자식 노드를 바꿔주는 while문을 반복한다.(이때 왼쪽 노드를 기준으로 비교 검사할 것이기 때문에 왼쪽 노드가 있을 때까지 라는 조건을 넣어준다.)
3. biggestChildIndex : currentIndex = 0 일 때 부 자식의 왼쪽 노드의 Indexr값을 변수로 지정해준다. 
4. 만약 자식의 오른쪽 노드가 있고, 자식의 오른쪽 노드가 왼쪽 노드보다 크다면 3. 의 date [biggestChildIndex]를 자식의 오른쪽 노드로 지정해준다. 
5. 4번의 조건이 불충분하면 자식의 왼쪽 노드가 더 크다는 뜻이므로 현재 heap배열의 최상단 노드가 date [biggestChildIndex](자식 왼쪽 노드) 보다 큰지 비교해준다. 
6. date [biggestChildIndex]가 더 크다면 swap()을 통해 서로 간의 노드 위치를 바꿔준다. 
7. 이후 새로운 위치에서의 비교 연산을 위해 currentIndex를 biggestChildIndex로 바꿔준다. 
   
   
   이 함수가 끝나면 다시 poll()로 돌아가게 되고 최종적으로 maxValue를 순서대로 리턴하게 된다. 

heapifyDown() {
    // index 0 최상위 요소
    let currentIndex = 0;

    // 현재 요소를 맨위에 놓고 자식이 더 크면 현재와 자식을 바꿔주는 while문 반복

    // 왼쪽 요소가 있는지 확인
    while (this.data[this.getLeftChildIndex(currentIndex)] !== undefined) {
      let biggestChildIndex = this.getLeftChildIndex(currentIndex);

      // 오른쪽노드와, 왼쪽 노드중 더 큰값을 biggestChildIndex 로 설정
      if (
        this.data[this.getRightChildIndex(currentIndex)] !== undefined &&
        this.data[this.getRightChildIndex(currentIndex)] >
          this.data[this.getLeftChildIndex(currentIndex)]
      ) {
        biggestChildIndex = this.getRightChildIndex(currentIndex);
      }

      // 자식노드가 더 크다면 부모노드랑, 자식노드랑 변경함
      if (this.data[currentIndex] < this.data[biggestChildIndex]) {
        this.swap(currentIndex, biggestChildIndex);
        currentIndex = biggestChildIndex;
      } else {
        return;
      }
    }
  }

최종 구현 코드 (Max heap)

// max heap 구현

class Heap {
  constructor() {
    this.data = [];
  }

  // 기본 셋팅
  getParentIndex(i) {
    return Math.floor(i - 1 / 2);
  }

  getLeftChildIndex(i) {
    return i * 2 + 1;
  }

  getRightChildIndex(i) {
    return i * 2 + 2;
  }

  swap(i1, i2) {
    const temp = this.data[i1];
    this.data[i1] = this.data[i2];
    this.data[i2] = temp;
  }

  // push 배열 끝에 넣기
  push(key) {
    this.data[this.data.length] = key;
    // 가장 큰 값일 수 있다. heap요구사항에 따라 자리를 바꿔줘야함 > hepifyUp()통해서 이뤄진다.
    this.heapifyUp();
  }

  // 인자 필요없다 항상 배열의 마지막 요소를 다루기 때문
  heapifyUp() {
    let currentIndex = this.data.length - 1;

    // current요소가 상위요소보다 클 때까지 돌린다.
    // 현재 요소 (가장마지막, 밑에있던 요소) 와 부모 요소의 값을 비교 한다. 현재요소가 크면 위로 올려야하기 때문에 swap()을 쓴다.
    while (
      this.data[currentIndex] > this.data[this.getParentIndex(currentIndex)]
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));

      // currentIndex를 비교했던 부보요소로 재할당시킨다.
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  // Push 뿐만아니라 poll도 할 줄 알아야 함(추출)

  poll() {
    // 가장 최상단 요소가 최댓값일 테고
    const maxValue = this.data[0];

    // 그 최상단 요소와 가장 아래에있는 요소로 대체한다. (제거해도되는데 여기서는 대체함)
    this.data[0] = this.data[this.data.length - 1];
    // 배열의 길이를 줄여 맨위에 할당했던 마지막 요소를 없애준다.
    this.data.length--;

    // 여전히 heap의 규칙인지 확인해야한다.
    // 이때 위에서부터 제일 아래로 실행되는 heapifyDown함수 실행
    // 위에서 끝에있던 요소를 첫번째로 대체했었기 때문에
    this.heapifyDown();

    return maxValue;
  }

  heapifyDown() {
    // index 0 최상위 요소
    let currentIndex = 0;

    // 현재 요소를 맨위에 놓고 자식이 더 크면 현재와 자식을 바꿔주는 while문 반복

    // 왼쪽 요소가 있는지 확인
    while (this.data[this.getLeftChildIndex(currentIndex)] !== undefined) {
      let biggestChildIndex = this.getLeftChildIndex(currentIndex);

      if (
        this.data[this.getRightChildIndex(currentIndex)] !== undefined &&
        this.data[this.getRightChildIndex(currentIndex)] >
          this.data[this.getLeftChildIndex(currentIndex)]
      ) {
        biggestChildIndex = this.getRightChildIndex(currentIndex);
      }

      if (this.data[currentIndex] < this.data[biggestChildIndex]) {
        this.swap(currentIndex, biggestChildIndex);
        currentIndex = biggestChildIndex;
      } else {
        return;
      }
    }
  }
}

---

Heap의 Big-O

삽입

• 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올린다.
• 완전 이진트리의 최대 높이는 O(logN) 이고, 반복하는 최대 횟수도 O(logN) 이 된다.

삭제 (추출)

• 원소를 맨 위에 넣어서 바닥까지 비교하면서 올린다.
• 완전 이진트리의 최대 높이는 O(logN) 이고, 반복하는 최대 횟수도 O(logN) 이 된다.

Big-O (시간 복잡도)	삽입	추출, 삭제
힙 (heap)	O(logN)	O(logN)

---