힙, 우선순위 큐의 차이?

힙 Heap

루트노드에 가장 큰 값 혹은 가장 작은 값을 저장하고 있는 완전 이진트리

힙 종류?

최대힙
루트노드가 가장 큰 값을 가진다. 따라서 값이 가장 큰 데이터가 우선적으로 제거됨

최소힙
루트노드가 가장 작은 값을 가진다. 따라서 값이 가장 작은 데이터가 우선적으로 제거된다.

힙 삽입
상향식으로 부모노드로부터 거슬로 올라가며 부모보다 자신의 값이 더 작은 경우에 위치를 교체함

힙 삭제
루트 노드자리에 가장 마지막 노드를 대체시키고 다른 위치로 변경시킨다.

시간복잡도

노드의 길이가 6개이지만 2번의 연산으로 힙성질을 유지시켜 O(logN)의 시간 복잡도를 가진다.

우선순위 큐 Priority Queue

우선순위가 높은 데이터가 먼저 나가는 구조
즉, 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조이다.
큐의 동작방식은 FIFO이다.
그리고 완전 이진트리이기때문에 중간에 비어있는 요소가 없다.
큐를 구현할 때는 각 노드에 인덱스 번호를 붙여서 인덱스로 생각을 하면 효과적으로 힙을 구현할 수 있다.

자식노드 구할 때
왼쪽자식노드index = (부모노드index)2
오른쪽자식노드index = (부모노드index)2+1
부모노드를 구하고 싶을 때
부모노드 index = 자식노드index/2