힙 정렬

이번에 소개할 정렬방식은 힙(Heap) 정렬입니다. 힙이란 보통 부모 노드가 자식 노드보다 큰 조건을 가진 완전 이진트리를 의미합니다. 힙에 대한 자세한 설명은 아래 링크를 참조해주세요.

2021.10.02 - [Programming/자료구조] - 힙 Heap

힙 Heap

---

1. 힙 정렬

힙 정렬은 전체 트리, 서브 트리에서 가장 큰 값이 부모 노드로 위치하는 트리 구조를 이용한 정렬 방식입니다. 힙에서 가장 큰 값을 가진 것이 루트이므로, 이 루트를 꺼내어서 배열에 차례대로 저장하면 정렬이 완료되는 방식을 갖고있습니다.

힙 정렬은 시간복잡도가 0(n log n)을 가지며 이 시간복잡도는 일정하게 유지됩니다.

다음과 같은 힙이 있을 때, 힙 정렬을 설명하겠습니다.

루트 노트인 7이 가장 크니까 7을 꺼내 기존 배열의 가장 마지막 인덱스로 보냅니다. 이때 배열에서 노란색 부분은 정렬된 부분이라고 가정합니다.

루트 노드를 제거 했더니 힙의 형태를 띄지 못하고 분해되었습니다. 이때 힙 정렬을 위한 힙의 형태를 만들기 위한 작업을 해주어야합니다.

그 방식은 다음과 같습니다.

우선, 힙에서 가장 마지막 요소(정렬되지 않은 부분의 가장 마지막 요소)를 루트 노드로 설정합니다.

하지만 이렇게 되면 루트가 가장 크다는 힙의 정의를 충족하지 못해 2를 옮겨주는 작업을 합니다.

이동된 루트 노드를 자식 노드와 비교해 더 큰 값의 자식노드와 자리를 바꿔줍니다. 이 작업을 더이상 이동하지 못할 때 까지 반복합니다. 위의 힙에서 이동을 하면 다음과 같이 됩니다. 배열 인덱스 또한 힙에 따라 변하게 됩니다.

이 과정을 모든 원소 삽입마다 반복해주면 힙 정렬이 완료됩니다.

 

 

 

2. 힙 정렬 구현

힙 정렬은 크게 정렬을 수행하는 부분과 힙을 구성하는 부분 두 가지로 나뉘어집니다.

우선 힙 정렬을 수행하는 heapSort 함수입니다. 각 정렬 횟수마다 힙을 구성하는 작업을 하고 정렬을 합니다. 

export const heapSort = arr => {
    //arr[0]의 요소를 인덱스 끝으로 보내는 정렬이므로
    //마지막 인덱스 부터 for문 조건 설정
    for (let i = arr.length - 1; i >= 0; i--) {
        //힙을 구성하도록 하는 함수 heapify
        arr = heapify(arr, i);

        //힙이 구성되었으면 정렬
        if (arr[0] > arr[i]) {
            let temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
        }
    }
    return arr;
};

 

다음은 힙 정렬에서 힙을 계속 구성하게 해주는 부분입니다.

const heapify = (arr, idx) => {
    let index = parseInt(idx / 2) - 1;
    let temp;

    //index가 0이면 더이상 정렬할 부분, 힙을 구성할 부분이 남아있지 않음!
    while (index >= 0) {
    	//마지막에서 -2번째 요소
        const left = arr[index * 2 + 1];
        //마지막에서 -1번째 요소
        const right = arr[index * 2 + 2];

        //앞쪽의 요소가 더 크면서 그 요소가 부모 요소보다 큰 경우
        //노드의 위치를 서로 바꾼다
        if (left >= right && arr[index] < left) {
            temp = arr[index];
            arr[index * 2 + 1] = temp;
            arr[index] = left;
        }
        //뒷쪽의 요소가 더 크면서 그 요소가 부모 요소보다 큰 경우
        //노드의 위치를 서로 바꾼다.
        else if (left < right && arr[index] < right) {
            temp = arr[index];
            arr[index * 2 + 2] = temp;
            arr[index] = right;
        }
        index--;
    }
    return arr;
};

 

전체 코드는 다음과 같습니다.

export const heapSort = arr => {
    for (let i = arr.length - 1; i >= 0; i--) {
        arr = heapify(arr, i);

        if (arr[0] > arr[i]) {
            let temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
        }
    }
    return arr;
};

const heapify = (arr, idx) => {
    let index = parseInt(idx / 2) - 1;
    let temp;

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

        if (left >= right && arr[index] < left) {
            temp = arr[index];
            arr[index * 2 + 1] = temp;
            arr[index] = left;
        }
        else if (left < right && arr[index] < right) {
            temp = arr[index];
            arr[index * 2 + 2] = temp;
            arr[index] = right;
        }
        index--;
    }
    return arr;
};

import {heapSort} from './study-code/sort/heap-sort.js';

let arr = [3, 4, 7, 1, 9, 2, 5, 8];

console.log(heapSort(arr));

---