Heap Sort

Heap Sort

STEP 1.

기존 배열을 가지고 MAX-heap이든, MIN-heap이든 힙의 형태로 만들어야 한다.

STEP 2.

Heap에서 자식 노드의 index를 통해 부모 노드 index 구하는 방법

여기서 부모 노드의 index를 찾는 방법은 heap을 나타내는 배열을 통해 쉽게 구할 수 있는데 (자신의 index) /2 에 올림을 한 후에 -1을 하면 자기 자신의 부모 노드의 index를 구할 수 있다.

Heap Insert

• Step 1. 일단 이진완전트리의 형태로 값을 넣는다. (배열의 마지막 index에 push_back한다.)

• Step 2. MAX-heap이라고 하면 재쉬함수 / 반복문으로 부모 노드를 계속 비교해 보면서, 만약 부모 노드가 자신 보다 작으면 값을 바꾼다.

Heap Pop

MAX heap이든 MIN heap이든 pop의 경우에는 힙의 index 0인 원소를 제거하게 된다.
Step 1. index 0번을 날린다.
Step 2. index 0을 날림과 동시에 힙의 마지막 원소를 index 0으로 가져온다.
* Step 3. 다시 힙을 재구성한다. 이 과정에서 heap insert와 다른 점은 자신의 자식 노드 2개를 비교해봐서 큰 거랑 (Max heap일 경우, Min heap일 경우 반대로 작은 놈이랑 바꾸기) 바꿔야 한다.

Heap을 배열로 구성하는 이유

1. 완전이진트리이기 때문에 중간에 비어있는 index가 없다.
2. 해당 노드의 index를 알면 간단한 연산을 통해 그 노드의 부모 노드 index를 구할 수 있다.
3. (2번과 연결) 노드의 index를 알면 random access를 통해 값을 알 수 있다.
4. 보통 부모 노드의 index를 쉽게 구하기 위해서 첫번째 index 0을 비워 놓는다.(그러면 부모의 index == 자식의 index/2로 간단하게 만들 수 있으므로)

Heapify

Heap의 특성을 만족하도록 각 노드들의 위치를 조정하는 과정

Heap의 정체는

heap의 구현도는 트리이다. 곧, heap은 배열로 표현가능하고 이 배열을 통해서 완전 이진트리를 만들면 우리가 생각하는 heap의 시각화가 가능한 것이다.

그래서 힙 정렬이란?

힙을 이용하여 정렬할 숫자들을 차례대로 insert 루 delete하여 값을 가져오면 임의의 숫자들을 정렬시킬 수 있다. 시간복잡도는 NlogN이다.

C++ STL heap

#include <iostream>
#include <vector>
#include <algorithm>

// Custom comparator functor
struct CustomCompare {
    bool operator()(int a, int b) const {
        // Define custom order: create a min-heap instead of the default max-heap
        return a > b;
    }
};

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    // Convert vector into a heap with custom comparator
    std::make_heap(vec.begin(), vec.end(), CustomCompare());

    std::cout << "Heap after make_heap with custom comparator: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Push a new element with custom comparator
    vec.push_back(7);
    std::push_heap(vec.begin(), vec.end(), CustomCompare());

    std::cout << "Heap after push_heap with custom comparator: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // Pop the top element with custom comparator
    std::pop_heap(vec.begin(), vec.end(), CustomCompare());
    int popped = vec.back();
    vec.pop_back();

    std::cout << "Heap after pop_heap with custom comparator: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << "\nPopped element: " << popped << std::endl;

    // Sort the heap with custom comparator
    std::sort_heap(vec.begin(), vec.end(), CustomCompare());

    std::cout << "Array after sort_heap with custom comparator: ";
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

C++ STL에서는 make_heap이라는 함수로 원본 배열을 heapify할 수 있다. 또한, CustomCompare라는 함수를 만들고 이의 function pointer를 make_heap의 parameter로 줄 수 있는데, 이를 통해 custom sorting이 가능한 heap을 생성할 수 있다.

우선순위 Queue

자료구조 이름에 "Queue"라는 단어가 붙어있어서 FIFO의 형태라고 생각할 수 있지만, 사실상 그렇지는 않다.

우선순위 queue에서는 먼저 들어오는 데이터가 아니라, 우선순위가 놓은 데이터가 먼저 나가는 형태의 자료구조이다.