6. 힙 (Heap) &우선 순위 큐

본 게시글은 책 : 면접을 위한 CS 전공지식 노트 (출판사 : 길벗, 주홍철 지음) 을 참조하여 작성하였습니다. + 구글링

---

*비선형 자료 구조 : 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조

 

◆  힙 (Heap)

- 완전 이진 트리 기반의 자료 구조이며  최소힙, 최대힙  두 가지가 있음

- 최대힙 : 루트 노드에 있는 값은 모든 자식 노드의 값들 중 가장 커야 함, 각 노드의 자식 노드들 또한 같은 속성

   ex )  99는 나머지 노드들 보다 높은 값

          88은 11, 22 보다 높은 값

최대힙

- 최대힙의 삽입 : 힙에 새로운 요소가 들어오면, 일단 새로운 노드들의 마지막 노드로 삽입 후 부모느들과의 크기를 비교하며 위치를 교환

   ex) 최대힙의 삽입- step 1 : 90을 마지막에 삽입

      최대힙의 삽입 - step 2 : 90 > 11 => 부모와 위치 교환

      최대힙의 삽입 - step 3 : 90 > 88 => 부모와 위치 교환

      최대힙의 삽입 - step 4 : 90 < 99 => 위치 교환 끝

- 최대힙의 삭제 : 최대힙에서 최댓값은 루트 노드 이므로 루트 노드를 삭제 후 정렬

     ex) 위 노드에서 최댓값 99 제거 후 정렬

- 최소힙 : 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값, 각 노드의 자식 노드들 또한 같은 속성

최소힙

---

◆  우선순위 큐

- 우선순위 대기열이라고도 하며, 우선 순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공되는 자료구조

- 우선순위 큐는 힙을 기반으로 구현 ( 힙은 일반적으로 배열을 이용하여 구현 )

- 아래 코드 처럼 greater를 써서 오름차순, less를 써서 내림차순 변경 가능 (C++)

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	priority_queue<int, vector<int>, greater<int>> PQueue1;		// 최소힙
	priority_queue<int, vector<int>, less<int>> PQueue2;		// 최대힙

	// 최소힙
	PQueue1.push(90);
	PQueue1.push(88);
	PQueue1.push(77);
	PQueue1.push(11);
	PQueue1.push(22);
	PQueue1.push(33);
	PQueue1.push(55);

	// 최대힙
	PQueue2.push(90);
	PQueue2.push(88);
	PQueue2.push(77);
	PQueue2.push(11);
	PQueue2.push(22);
	PQueue2.push(33);
	PQueue2.push(55);

	// 최소힙 우선순위 출력
	cout << PQueue1.top() << endl;
	// 최대힙 우선순위 출력
	cout << PQueue2.top() << endl;

	return 0;
}

참고로 prority_queue <int> 요렇게만 작성하면 최대힙을 기본으로 자료형이 선언됩니다! 

 

위의 글과 관련하여 추가적인 내용이나 피드백은 언제나 환영입니다 :)