Heap

자료구조 중 힙(Heap)에 대해 정리해보자. 힙(Heap)이란? 자료구조 중 힙(Heap)은 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조이다. Heap은 일반적으로 이진 힙(binary heap)으로 구현되며, 우선순위 큐(priority queue)와 같은 다른 추상 자료형의 구현에 주로 사용된다. Heap은 다음과 같은 특징을 가지고 있다. 완전 이진 트리(Complete Binary Tree) : Heap은 완전 이진 트리의 형태를 가진다. 이는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태를 말한다. 부모-자식 노드 관계 : Heap의 부모 노드는 항상 자식 노드보다 우선순위가 높거나 같은 값을 가집니다. 이러한 특성은 최대..

우선순위 큐(Priority Queue)와 힙(Heap)에 대해 간단히 알아보자. 우선순위 큐(Priority Queue)란? 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. 어떤 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. ex) 상품 데이터를 자료구조에 넣었다가 비싼(가치가 높은) 상품부터 꺼내서 조회할 경우 : 이 때 상품의 가치를 상품과 함께 저장해 추출 시 가치가 높은 상품부터 꺼내도록 한다. 여기서 다시 한 번 스택(Stack), 큐(Queue), 우선순위 큐(Priority Queue) 자료구조를 비교/정리해보고 가자. 자료구조 가장 먼저 추출되는 데이터 스택(Stack) 가장 나중에 삽입된 데이터(후입선출) 큐(Queue) 가장 먼저 삽입된 데이터(선입선출) 우선순..