힙정렬
우선순위 큐를 위해 만들어진 자료구조
완전 이진트리의 일종, 우선순위 큐를 위해 만들어진 자료구조
모든 데이터 정렬이 아닌 최댓값 몇몇개, 최솟값 몇몇개 뽑아낼때 유리하다
자료구조/삭제되는 요소
스택 - 가장 최근에 들어온 데이터
큐 - 가장 먼저 들어온 데이터
우선순위큐 - 가장 우선순위가 높은 데이터
힙은 일종의 반정렬상태를 유지함
- 큰값이 상위레벨, 작은값이 하위레벨에 있는 느슨한 정렬상태
- 부모노드의 키값이 자식노드의 키 값보다 항상 큰 이진트리
중복된 값을 허용한다.(이진탐색트리에서는 중복된 값을 허용하지않음)
<구현>
표준적 자료구조는 배열
편한 구현을 위해 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연산
'TIL' 카테고리의 다른 글
Nest) request Query nullable 명시했으나 오류가 생기는 문제 (0) | 2024.04.18 |
---|---|
GCP Compute Engine 이용해 서버 배포하기 (0) | 2024.04.16 |
이모지 문자 mySql에 저장하기 (0) | 2024.04.12 |
TIL #34) Nest로 S3 이용하기 (0) | 2024.03.25 |
TIL #33) 순서 정렬하기 (0) | 2024.03.22 |