C++로 구현하는 자료구조 (8) - Heap

C++로 구현하는 자료구조

이번 포스팅에서는 힙 자료구조를 알아보려고 한다. 힙은 우선순위 큐로도 활용할 수 있으며, 정렬에도 사용할 수 있다. 힙에 대한 이해도가 낮아서 geeksforgeeks의 구현 예제를 많이 참고했다. 어떤 자료구조인지 함께 알아보자!

 

---

1. Heap

출처 : https://www.geeksforgeeks.org/binary-heap/

힙은 완전이진트리(complete binary tree)를 기본으로 한 트리형 자료구조이다. 최댓값과 최소값을 빠르게 찾아내기 위해 고안되었으며, 종류에 따라 다음과 같은 속성을 지닌다.

 

• 최소 힙이라면?
  • 자식 노드의 값은 부모 노드의 값보다 크다.
• 최대 힙이라면?
  • 자식 노드의 값은 부모 노드의 값보다 작다.

이런 속성을 만족하면 힙의 루트는 최대 혹은 최소값이 된다.

 

 

2. Heap 구현방법

처음 힙을 구현하려고 했을 때, 이번 포스팅에서 구현했던 이진탐색트리와 같은 방법으로 구현하려고 접근했었다. 그러나 그런 방법보다 동적배열을 사용하면 훨씬 간단하게 힙을 구현할 수 있다. 아래의 노트 특성을 기억하면 손쉽게 힙을 구현할 수 있다. 편의상 힙의 자료를 담는 배열을 Arr라고 하겠다.

 

1. 힙의 루트는 Arr[0]이다.
2. 힙의 각 i번째 노드들은 아래와 같은 성질을 만족한다.
   • Arr[(i-1) / 2]은 i번째 노드의 부모 노드이다.
   • Arr[(2*i) + 1]은 i번째 노드의 왼쪽 자식 노드이다.
   • Arr[(2*i) + 2]은 i번째 노드의 오른쪽 자식 노드이다.

 

위에서 기술한 성질들을 이용하면 배열을 통해 힙을 구현할 수 있으며, 힙 정렬을 수행할 때에도 위의 성질을 이용하여 정렬을 수행할 수 있다.

 

 

3. 소스코드

#pragma once
#include <vector>
#include <algorithm>
#include <iostream>

/*
Reference:
https://www.geeksforgeeks.org/binary-heap/
*/

template <typename T>
class Heap {
private:
    std::vector<T> heap;

    // 주어진 인덱스의 부모 인덱스를 가져온다.
    int _parent(int idx) {
        return (idx - 1) / 2;
    }

    // 주어진 인덱스의 왼쪽 인덱스를 가져온다.
    int _left(int idx) {
        return (2 * idx + 1);
    }

    // 주어진 인덱스의 오른쪽 인덱스를 가져온다.
    int _right(int idx) {
        return (2 * idx + 2);
    }

    void _heapify(int idx) {
        int l = this->_left(idx);
        int r = this->_right(idx);

        int largest = idx;
        if (l < heap.size() && heap[l] > heap[idx]) {
            largest = l;
        }

        if (r < heap.size() && heap[r] > heap[largest]) {
            largest = r;
        }

        if (largest != idx) {
            std::swap(heap[idx], heap[largest]);
            this->_heapify(largest);
        }
    }

public:
    Heap() {}

    void insert(T data) {
        heap.push_back(data);
        int idx = heap.size() - 1;

        // 부모 인덱스가 자식 인덱스보다 작다면 교환한다.
        while (idx != 0 && heap[this->_parent(idx)] < heap[idx]) {
            std::swap(heap[idx], heap[this->_parent(idx)]);
            idx = this->_parent(idx);
        }
    }

    void pop() {
        if (heap.size() <= 0) {
            std::cout << "힙에 요소가 없습니다." << std::endl;
            return;
        }

        // 루트 요소를 맨 뒤로 보내고 heapify를 수행한다.
        int root = heap[0];
        heap[0] = heap[heap.size() - 1];
        heap.pop_back();
        this->_heapify(0);

        return;
    }

    T top() {
        return heap[0];
    }

    ~Heap() {
        delete heap;
    }
};

#include <iostream>
#include "datastructure/Heap.h"

int main() {

    Heap<int>* heap = new Heap<int>();
    heap->insert(3);
    heap->insert(1);
    heap->insert(5);
    heap->insert(2);
    heap->insert(8);

    std::cout << heap->top() << std::endl; // 8

    heap->pop();
    std::cout << heap->top() << std::endl; // 5

    return 0;
}