2025-01-03 우선순위 큐(Priority Queue), 힙

힙을 배우기전 잠깐 우선순위 큐를 확

 

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지며, 높은 우선순위를 가진 요소가 먼저 처리되는 데이터 구조입니다.

 

 

우선순위 큐의 개념

정의: 

우선순위 큐는 FIFO(First In First Out) 방식에 따라 동작하는 일반적인 큐와는 달리, 각 요소에 우선순위를 부여하고, 우선순위가 높은 요소가 먼저 나오는 큐입니다.

용도:

 주로 작업의 우선순위를 관리해야 할 때 사용됩니다. 예를 들어, 운영 체제의 작업 스케줄링, 그래프 알고리즘(다익스트라 알고리즘) 등에서 사용됩니다.

우선순위 큐의 동작 방식

삽입 (Insert): 

새로운 요소를 큐에 추가할 때, 해당 요소의 우선순위를 함께 정의합니다.
삭제 (Remove): 

가장 높은 우선순위를 가진 요소를 삭제합니다. 동점인 경우에는 먼저 들어온 순서에 따라 처리됩니다.

 

.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 최대 힙으로 구현된 우선순위 큐
    priority_queue<int> pq;

    // 요소 삽입
    pq.push(5);
    pq.push(1);
    pq.push(3);
    pq.push(4);
    pq.push(2);

    // 요소 제거
    cout << "우선순위 큐의 요소 (우선순위 높은 순서): " << endl;
    while (!pq.empty()) {
        cout << pq.top() << " "; // 가장 높은 우선순위의 요소 출력
        pq.pop(); // 요소 제거
    }
    cout << endl;

    return 0;
}

 

자동 정렬이 된다는점은 좋은것 같습니다.

힙 (Heap)

정의
힙은 특별한 형태의 완전 이진 트리로, 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구분됩니다. 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 크고, 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 작습니다.

 

 

힙의 종류

최대 힙 (Max Heap):

부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.
루트 노드에는 가장 큰 값이 위치합니다.

최소 힙 (Min Heap):

부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
루트 노드에는 가장 작은 값이 위치합니다.

 

힙의 성질

완전 이진 트리: 힙은 항상 완전 이진 트리입니다. 즉, 모든 레벨이 가득 차 있어야 하며, 마지막 레벨의 노드는 왼쪽부터 차례로 채워져야 합니다.

 

최대힙

 

#include <iostream>
#include <vector>

using namespace std;

class MaxHeap {
public:
    vector<int> heap;

    void insert(int value) {
        heap.push_back(value); // 마지막 위치에 추가
        int index = heap.size() - 1;
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (heap[index] > heap[parentIndex]) {
                swap(heap[index], heap[parentIndex]);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    void deleteRoot() {
        if (heap.empty()) return;
        heap[0] = heap.back(); // 마지막 요소를 루트로 이동
        heap.pop_back(); // 마지막 요소 제거
        heapify(0);
    }

    void heapify(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;

        if (leftChild < heap.size() && heap[leftChild] > heap[largest]) {
            largest = leftChild;
        }
        if (rightChild < heap.size() && heap[rightChild] > heap[largest]) {
            largest = rightChild;
        }
        if (largest != index) {
            swap(heap[index], heap[largest]);
            heapify(largest);
        }
    }

    void printHeap() {
        for (int value : heap) {
            cout << value << " ";
        }
        cout << endl;
    }
};

int main() {
    MaxHeap maxHeap;
    maxHeap.insert(5);
    maxHeap.insert(1);
    maxHeap.insert(3);
    maxHeap.insert(4);
    maxHeap.insert(2);

    cout << "힙의 요소: ";
    maxHeap.printHeap();

    maxHeap.deleteRoot();
    cout << "루트 삭제 후 힙의 요소: ";
    maxHeap.printHeap();

    return 0;
}

 

 

글쓴이의 분석

먼저 메인 부터 봐서 흐름을 찾아봅니다.

 

MaxHeap maxHeap;
    maxHeap.insert(5);

...

    maxHeap.printHeap();
    maxHeap.deleteRoot();
    cout << "루트 삭제 후 힙의 요소: ";

 

 

MaxHeap

 

public:
    vector<int> heap; // int 배열

 

void insert(int value)

힙에 마지막위치에 추가

// 1개는 반복문 조건 해당안하니 2개부터 예로들음

인덱스 정하고                                                 // int index = heap.size() - 1;              //  2 -1  == 1;

반복 문 인덱스 보다 0이 작을때까지

부모인덱스 구하기                                          // int parentIndex = (index - 1) / 2;    //      0

만약 새로 추가한 데이터가 부모 인덱스보다 클경우

교체 그리고 

// 원래 인덱스가 3개였다고  예로들면 (3- 1 ) / 2  == 1 부모 인덱스는 1  자식인덱스는 3

인덱스를 부모 인덱스로 교체  

 

 void deleteRoot() 

마지막 요소를 루트로 이동! 하여 아예 덥어쓰는방식 으로 지우고 마지막 요소를 제

맨뒤를 삭제 하는방식

heapify(0); 으로 이동 

 

 

void heapify(int index) 

해당 인덱스의 왼쪽자식 오른쪽 자식 구하기

2 * index  + 1 or 2;

가장 큰 largest (사실상 최상위 인덱스 매개변수 그자체 )

 

아래 조건문들은 else if가 아니므로 3번의 조건 전부 확인

 

자식 노드가 힙의 갯수보다 작고 왼쪽 자식의 값이 힙의 인덱스보다 크다면

인덱스보다 크니 lagest변경 

그렇지만 오른쪽이 더크면 오른쪽으로 변경

 

마지막으로 가장큰값이 인덱스가 아닌경우 즉 가장 큰 값이 바뀐경우

자리를 변경해줍니다.

그러고 그 변경된 인덱스로 다시 heapify 실행

 

위 함수 내용 : 

위의코드를실행하면

힙의 요소: 5 4 3 1 2
루트 삭제 후 힙의 요소: 4 2 3 1

이렇게 정렬이된것 처럼 보이지만 아직 완벽하게 정렬한것은아니다

힙도 이진트리이기 때문에 5에서 자식 2개 4 3

또 4의 자식인 1과 2순으로 자식노드가 다차면 왼쪽 노드에서 부터
다시 자식이 생성 되는 방식으로 되어있습니다.

이진 탐색트리랑은 다르게 최대힙 기준으로는 부모노드가 자식노드보다 크면 되고

자식관의 크기 관계가 중요하지않습니다.

차이점 이였습니다.

 

 

위의 코드 값 
힙의 요소: 5 4 3 1 2
루트 삭제 후 힙의 요소: 4 2 3 1

 

* 조사하면서 알게된 정보는 벡터에서 pop을하면 할당된 메모리가 해제된다고 하는데 더 알아봐야할듯합니다.

 

 

최소힙

정의:

최소 힙은 완전 이진 트리의 형태를 가지며, 모든 부모 노드의 값이 자식 노드의 값보다 작거나 같은 특성을 가집니다. 즉, 루트 노드에는 가장 작은 값이 위치합니다.

 

 

#include <iostream>
#include <vector>

using namespace std;

class MinHeap {
public:
    vector<int> heap;

    // 요소 삽입
    void insert(int value) {
        heap.push_back(value); // 마지막 위치에 추가
        int index = heap.size() - 1;
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            // 부모 노드와 비교하여 작은 값을 위로 이동
            if (heap[index] < heap[parentIndex]) {
                swap(heap[index], heap[parentIndex]);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    // 루트 삭제
    void deleteRoot() {
        if (heap.empty()) return;
        heap[0] = heap.back(); // 마지막 요소를 루트로 이동
        heap.pop_back(); // 마지막 요소 제거
        heapify(0); // 힙의 성질 유지
    }

    // 하향 조정
    void heapify(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int smallest = index;

        // 자식 노드와 비교하여 작은 값을 위로 이동
        if (leftChild < heap.size() && heap[leftChild] < heap[smallest]) {
            smallest = leftChild;
        }
        if (rightChild < heap.size() && heap[rightChild] < heap[smallest]) {
            smallest = rightChild;
        }
        if (smallest != index) {
            swap(heap[index], heap[smallest]);
            heapify(smallest);
        }
    }

    // 힙의 요소 출력
    void printHeap() {
        for (int value : heap) {
            cout << value << " ";
        }
        cout << endl;
    }
};

int main() {
    MinHeap minHeap;
    minHeap.insert(5);
    minHeap.insert(1);
    minHeap.insert(3);
    minHeap.insert(4);
    minHeap.insert(2);

    cout << "최소 힙의 요소: ";
    minHeap.printHeap();

    minHeap.deleteRoot();
    cout << "루트 삭제 후 최소 힙의 요소: ";
    minHeap.printHeap();

    return 0;
}

 

void insert(int value)

최대값과 비슷하지만 if조건문에서 작은값을 위로 보냄

 

 void deleteRoot()

똑같이 루트를 맨뒤에 요소로 덮어씀

 

void heapify(int index)

자식 노드 2개 와 가장 작은 값 정해놓음

 

누가더작은지 비교후 교체 

최대힙과 같지만 적은값을 앞으로 혹은 위로 올리는 방식

 

 

힙의 시간 복잡도

 

삽입: O(log n)
새로운 요소를 힙에 추가할 때, 요소를 배열의 끝에 추가한 후 상향 조정을 통해 힙의 성질을 유지합니다. 이 과정에서 최대 높이만큼 이동해야 하므로 O(log n)입니다.

삭제 (루트 삭제): O(log n)
루트 노드를 삭제할 때, 마지막 요소를 루트로 이동시키고 하향 조정을 통해 힙의 성질을 유지합니다. 이 역시 최대 높이만큼 이동해야 하므로 O(log n)입니다.

최소/최대 조회: O(1)
최소 힙에서는 루트가 가장 작은 요소, 최대 힙에서는 루트가 가장 큰 요소이므로, 이를 조회하는 것은 O(1)입니다.

 

장점

빠른 우선순위 처리:
힙은 우선순위 큐를 구현하는 데 매우 효율적이며, 높은 우선순위를 가진 요소를 빠르게 처리할 수 있습니다.

동적 데이터 구조:
힙은 동적으로 크기가 조정되는 배열(벡터)을 사용하여 구현되므로, 메모리 사용이 유연합니다.

정렬 기능:
힙 정렬(Heap Sort) 알고리즘을 사용하여 O(n log n) 시간 복잡도로 정렬할 수 있습니다.

 

단점

비순차적 접근:
힙은 배열 형태로 저장되지만, 요소 간의 관계가 비순차적이므로 순차적으로 접근하는 것이 어렵습니다. 이로 인해 배열처럼 인덱스를 통해 직접 접근하기 힘듭니다.

상수 시간 복잡도 부족:
최소/최대 값을 조회하는 것은 O(1)이지만, 특정 요소를 검색하거나 삭제하는 것은 O(n)입니다. 이는 다른 자료구조(예: 해시 테이블)와 비교했을 때 단점이 될 수 있습니다.

메모리 사용:
힙은 완전 이진 트리를 유지하기 위해 추가적인 메모리 공간을 필요로 할 수 있습니다. 특히, 비어 있는 노드도 배열에서 차지하므로 메모리 낭비가 발생할 수 있습니다.

 

 

힙은 우선순위 큐를 표현하는 방식입니다.

배열과는 다르게 중간의 인덱스를 꺼내쓰는 용도가아닌

사용할 순서가 정해져야할 경우사용됩니다.

그러므로 단점중 하나인 인덱스를 통해 직접 접근하는용도로 사용하는 게 아닙니다.

 

제가 찾은 방식은 배열을 사용했기때문에 이진 탐색 트리 와는 다릅니다.

연속적인 메모리를 사용한다는 점에서 배열의 장점인 빠른 메모리 접근 속도를 얻고

단점인 메모리 낭비도가지고 있습니다.