힙 정렬

힙정렬
우선순위 큐를 위해 만들어진 자료구조
완전 이진트리의 일종, 우선순위 큐를 위해 만들어진 자료구조
모든 데이터 정렬이 아닌 최댓값 몇몇개, 최솟값 몇몇개 뽑아낼때 유리하다

자료구조/삭제되는 요소
스택 - 가장 최근에 들어온 데이터
큐 - 가장 먼저 들어온 데이터
우선순위큐 - 가장 우선순위가 높은 데이터

힙은 일종의 반정렬상태를 유지함
- 큰값이 상위레벨, 작은값이 하위레벨에 있는 느슨한 정렬상태
- 부모노드의 키값이 자식노드의 키 값보다 항상 큰 이진트리
중복된 값을 허용한다.(이진탐색트리에서는 중복된 값을 허용하지않음)

<구현>
표준적 자료구조는 배열
편한 구현을 위해 0은 사용하지않음
새로운 값이 추가되면 아래인덱스부터 비교해 교환해나간다.

부모노드=i
왼쪽 자식노드=2i
오른쪽 자식노드=2i+1

8번을 11번 자리에 넣으면

<핵심?>
추가할때는 마지막 노드에 넣고
삭제할떄는 루트노드를 삭제하고, 가장 마지막 값을 루트노드에 넣는다

 

//heap 정렬

function main() {
  arr = heapsort(arr);
  console.log(arr);
}

function heapSort(arr) {
  //마지막 인덱스값부터 시작!
  for (let i = arr.length - 1; i > 0; i--) {
    arr = heapify(arr, i);
  }
}

//본격적으로 힙비교
function heapify(arr, lastIdx) {
  //부모노드 인덱스
  let idx = parseInt(lastIndx / 2) - 1;

  while (idx >= 0) {
    const left = arr[idx * 2];
    const right = arr[idx * 2] + 1;

    //왼.자식노드가 오른쪽보다 크거나 같고, 부모노드보다 크다면,
    //왼쪽 자식노드를 부모노드로 옮긴다
    if (left >= right && arr[idx] < left) {
      //부모노드
      temp = arr[idx];
      //왼쪽자식노드는 부모노드에
      arr[idx * 2] = temp;
      //부모노드위치에 왼.자식노드넣음
      arr[idx] = left;
    }
  }
}

//힙 생성 알고리즘을 이용해 최대힙을 만듬
//최대힙의 루트노드와 맨 끝을 비교해서 더 큰값을 아래에 내림(젤 마지막 인덱스는 젤큰값이라 인정함)
//고로 마지막인덱스값은 5가아니라 4가됨(더이상 비교안할거임)
//두번째 돌때는 또 루트노드와 마지막인덱스 -1값을 비교해서 서로 스와핑
//비교연산을 하는 노드의 인덱스를 정하는 방식은 배열의 길이/2연산