[C++] 자료구조 - 힙(Heap)

힙 (Heap)   

 

힙(Heap)은 완전 이진 트리에 있는 노드 중에서 값이 가장 큰 노드나 값이 가장 작은 노드를 찾기 위해 만든 자료구조다. 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap), 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다. 힙은 우선순위 큐(Priority Queue)라고도 한다. STL에서는 std::priority_queue로 구현이 되어 있다.

 

std::priority_queue - cppreference.com

 

 

STL / 힙   

# include <queue> 를 이용해서 사용이 가능하다. 선언방법은 아래와 같다.

std::priority_queue<int> maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

 

힙의 불변성   

   - 최대 / 최소 원소에 즉각적으로 접근이 가능해야 한다. (최대 / 최소 원소는 항상 루트 노드에 존재한다.)

   - 부모 노드가 자식 노드보다 항상 크거나(Max Heap), 작아야 한다(Min Heap).

 

연산   

  - 검색  / 읽기 : 최대 / 최소 원소에 대해서만 가능  /   O(1)

  - 삽입 : 완전 이진트리이므로   /   O(logN)

  - 삭제 : 최대/최소 원소에 대해서만 가능  /  O(logN)

 

 

힙 구현   

 

push

먼저 push_back함수를 이용해서 맨 끝에 데이터를 삽입한다.  자식 인덱스는 size()함수를 이용해 초기화 시켜준다.

첫번째 노드를 1로 생각하고 다음 자식인덱스를 2로 나누어 부모노드를 찾는다. 

 

인덱스의 제한 범위는 벡터size() -1이기 때문에 인덱스 -1을 시켜주어 부모노드와 비교한다.

부모노드가 자식보다 작으면 부모노드와 자식노드를 바꿔주고, 이 과정을 부모노드가 자식노드보다 커지는 시점까지 반복을 한다.

 

 

 

 

 

아래는 Heaptest.cpp에서 실행시킨 push과정이다. 완성된 트리와, 트리가 완성될때까지 배열의 과정을 표현해보았다.

 

 

pop

마지막 노드를 벡터의 back함수를 이용해서 루트 노드로 가져온다. 그리고 pop_back을 이용해서 마지막 노드를 제거한다.
스왑 대상이되는 루트노드를 1로 초기화 시키고, left자식노드는 2n, right자식노드는 2n+1을 해준다.

부모가될 노드와 스왑하기 위한 child변수를 선언하고 왼쪽 자식하고 오른쪽 자식 중 더 큰 쪽을 child변수에 대입한다. 선택된 child 인덱스와 부모인덱스와 스왑을 해준다. 이과정을 반복하는데 예외처리가 몇가지 존재한다.

첫번째 경우는 현재 힙의 사이즈가 1이하일때이다, 이럴경우 루트노드만 존재하는 상태이고 자식이 없는 상태이므로 break를 시켜준다. 

두번째 경우는 부모가 자식보다 클경우, 즉 힙의 불변성을 만족하는 경우이다.
이 경우에는 아까전에 설명한 push함수와 비슷한 탈출조건이므로 역시 break를 시켜준다.

 

 

 

 

 

Top / Empty / Size

각각 벡터의 함수인 front(), empty(), size()를 활용해서 바로 리턴시켜주면 된다.

 

 

Heap.h

#pragma once

#include <vector>


// 완전 이진트리
// [][][][][][][][][][]
// 1             : Root Node
// Index * 2     : Left
// Index * 2 + 1 : Right

class Heap
{
public:
    Heap() = default;
    ~Heap() = default;

    // 힙의 가장 큰 원소를 반환한다.
    const int& top() const;

    // 힙이 비었는지 체크한다.
    bool            empty() const;

    // 힙의 크기를 반환한다.
    size_t          size() const;

    // 힙에 값을 삽입한다.
    void            push(int value);

    // 힙에서 값을 제거한다.
    void            pop();
private:
    std::vector<int>     _container;
};

 

 

Heap.cpp

#include "Heap.h"
#include <algorithm>

const int& Heap::top() const
{
	return _container.front();
}

bool Heap::empty() const
{
	return _container.empty();
}

size_t Heap::size() const
{
	return _container.size();
}

void Heap::push(int value)
{
	// 1. 먼저 맨 끝에 데이터를 삽입한다.
	_container.push_back(value);

    // 1-1. 자식노드의 인덱스에 size()값을 대입한다.
	size_t currentIndex = size();
    
    // HACK : 첫번째 노드를 1로 생각
	// 2. 힙의 불변성을 만족할 때 까지 데이터를 바꿔준다.
	while (currentIndex > 1)
	{
		// 2-1. 부모 노드를 찾는다.
		size_t parentIndex = currentIndex / 2;

		// 2-2. 부모 노드와 비교한다.
		if (_container[parentIndex - 1] >= _container[currentIndex - 1])
		{
			// 2-2-1. 부모가 나보다 더 크다면 힙의 불변성을 만족하는 것이므로 종료
			break;
		}

		std::swap(_container[parentIndex - 1], _container[currentIndex - 1]);

		currentIndex = parentIndex;
	}
}

void Heap::pop()
{
    //1. 마지막 노드를 루트 노드로 가져온다.
    _container[0] = _container.back();

    //2. 마지막 노드를 제거한다.
    _container.pop_back();

    //2-1. 사이즈를 초기화하고 루트(부모)노드를 1로 초기화한다.
    const size_t currentSize = _container.size();
    size_t currentIndex = 1;

    //3. 힙의 불변성을 만족할 때까지 자식이랑 바꾼다.
	while (true)
	{
		size_t left = currentIndex * 2;
		size_t right = left + 1;

		// 3-1. 자식이 존재해야 한다.
		if (left > currentSize)
		{
			break;
		}

		// 3-2. 왼쪽 자식하고 오른쪽 자식 중 더 큰 쪽으로 바꾼다.
		size_t child = left;
		if (right <= currentSize && _container[left - 1] < _container[right - 1])
		{
			child = right;
		}

		// 3-3. 바꿀 자식이 없다면 종료한다.
		if (_container[currentIndex - 1] >= _container[child - 1])
		{
			break;
		}

		std::swap(_container[currentIndex - 1], _container[child - 1]);

		currentIndex = child;
	}

}

 

Heaptest.cpp

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

#include <queue>

int main()
{
	Heap heap;

	for (int num : {7, 4, 11, 1, 0, 27, 31, 12, 5, 6})
	{
		heap.push(num);
	}

	while (heap.size())
	{
		std::cout << heap.top() << " ";
		heap.pop();
	}
	return 0;
}