본문 바로가기

힙

[C] 힙과 우선순위 큐
coding/Data Structure(C) 2020. 12. 13. [C] 힙과 우선순위 큐 힙(Heap)과 우선순위 큐(Priority Queue)에 대해 알아보자. 1. 힙 (Heap) 여기서 배우는 힙은 메모리상의 힙이 아니다!!! 자료구조의 첫장 안에 코드, 데이터, 스택, 힙 영역이 있다는 건 배웠을 것이다. 하지만 이 힙은 힙 정렬을 배우기 위한 자료구조 구현 방법이다. 밑에 우선순위 큐를 구현하기 위해 힙을 이용한다. 힙이란 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 예를 들어, 가장 큰 값을 빠르게 찾기 위해선 다음과 같은 최대 힙 트리를 만드는 게 좋다. 잘 보면 우리가 지금까지 배워오던 이진트리와는 아주 다르다. 이진트리는 루트노드를 기준으로 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 배정된 형태이다. 최대 힙 ..

티스토리툴바