Algorithm - Heap

힙(Heap)이란?

주어진 데이터들 중에서 특정 기준에 적합한 '최댓값' 혹은 '최솟값'을 빠르게 찾는

완전이진트리 를 기반으로 한 자료구조이다

이를 사용하여 우선순위큐(Priority Queue)를 구현가능하다

 

특징

시간복잡도 : 최소 , 평균 , 최악 시간 복잡도 전부 0(N * LogN)

이유 : 새로운 데이터의 삽입은 O(1)이 걸림 그다음 부모의 노드와 비교하여 새 데이터가 부모보다 크다면

둘의자리를 바꿈, 이 과정을 자신보다 큰 부모를 만날떄까지 반복 힙은 데이터 N개의 비해 높이가 로그N인

완전 이진트리를 유지 함, 그래서 최악의 경우인경우도 비교의 교환 과정은 트리의 높이만큼만 일어남

간단하게 설명해서 힙의 높이가 로그N에 가까운 이유는 트리의 레벨이 하나 깊어질떄마다

저장 가능한 노드의 수가 두배씩 늘어나는 구조이기때문에 반대로 말하면 데이터의 갯수가 두배로 늘어나도

높이는 겨우 1만 증가함

 

종류 : 최대힙, 최소힙

최대힙 : 부모가 항상 자식의 노드보다 큰 경우 즉 루트가 제일 숫자가 큰 경우

최소힙 : 부모가 항상 자식의 노드보다 작은 경우 즉 루트가 가장 숫자가 작은 경우

 

완전이진트리 에서 최대힙의 경우 이진트리의 생성과정

Heapify 함수 (힙 생성 알고리즘) 를 수행하여 부모와 자식 노드를 비교하여 Swap을 진행한다

왼쪽부터 채워나가는 형식이며 부모가 자식보다 작은경우 자리를 변경한다

 

사용 헤더파일

#include <algorithm>
#include <queue>

 

기존 배열/벡터를 힙으로 변환

make_heap(begin(), end());

 

마지막에 삽입한 원소릴 힙에 맞게 재배치

push_heap(begin(), end());

 

 

루트(최댓값 or 최솟값)을 끝으로 보냄 / pop_back()으로 제거

pop_heap(begin(), end());

 

힙 전체 정렬 수행

최대힙의 경우

vector<int> v = {3, 4, 1, 1, 5 };
make_heap(v.begin(), v.end());
cout << " 최대힙의 루트(최댓값): " << v.front() << endl;

//오름차순 힙정렬
sort_heap(v.begin(), v.end());
cout << "정렬된 최대힙: " ;
for(int x : v)
{
	cout << x << " ";
}
return 0;

최소힙의 경우

vector<int> v = {3, 4, 1, 1, 5};
    make_heap(v.begin(), v.end(), greater<int>());
    cout << "최소힙 루트(최소값) : " << v.front() << endl;

    sort_heap(v.begin(), v.end(), greater<int>());
    cout << "정렬된 최소힙: ";
    for(int x : v) {
        cout << x << " ";
    }
    cout << endl;

    return 0;

 

사용예시

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> v = { 3, 1, 4, 1, 5 };

	//힙 만들기 (이번경우는 최대힙)
	make_heap(v.begin(), v.end());
	cout << "최댓값 : " << v.front() << endl;

	//새로운값 추가하기
	v.push_back(10);
	//힙 재정렬
	push_heap(v.begin(), v.end());
	cout << "정렬된 최댓값 : " << v.front() << endl;

	//힙에서 값을 꺼내는 경우 (내부적으로 루트와 벡터의 마지막 원소를 교환 최대값이 v.back으로 이동))
	pop_heap(v.begin(), v.end());
	cout << "내가 꺼낸값 : " << v.back() << endl;
	//실제로 제거 []범위 조정 (루트값 꺼내는법)
	v.pop_back();
	
	//모든원소를 완전히 정렬
	sort_heap(v.begin(), v.end());
	for (int x : v)
	{
		cout << x << " ";
	}
	
}

 

출력값

 

우선순위큐(Priority Queue)사용예제

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() 
{
    //최소힙 우선순위 큐 만들기
    priority_queue<int, vector<int>, greater<int>> minPq;

    minPq.push(10);
    minPq.push(5);
    minPq.push(20);

    while (!minPq.empty()) 
    {
        cout << minPq.top() << " ";
        minPq.pop();
    }
    cout << endl;

    return 0;
}