[영상후기] 우선순위 큐와 힙의 개념과 차이, 사용 사례를 설명합니다! 힙이 어떻게 동작하는지도 예를 통해 자세히 설명합니다!

Priority queue(우선순위 큐) : 큐와 유사하지만 우선순위가 높은 아이템이 먼저 선택

주요 동작
1) insert : 아이템에 우선순위 정보를 같이 넣어줘야 함
2) delete : 큐에서 가장 우선순위가 높은 아이템을 빼네는 것
3) peek : 빼내기는 하지만 우선순위큐에서 제거는 하지 않음

heap : 이진트리 기반으로 구현
-> max heap : 부모노드의 키가 자식노드의 키보다 크거나 같은 트리
-> min heap : 부모노드의 키가 자식노드의 키보다 작거나 같은 트리

힙의 주요 동작

• insert :힙에 아이템 집어 넣기(키값 같이 넣어줘야 함)
• delete : 키값이 가장 큰(작은) 아이템 끄집어 내기
  • 루트노드가 가장 큰 것(max heap)
  • 루트노드가 가장 작은 것(min heap)
• peek : 키값이 가장 큰(작은) 아이템 끄집어 내기(실제로 힙에서 삭제하지는 않는다)

힙의 키를 우선순위로 사용한다면, 힙은 우선순위큐의 구현체가 된다.

Priority queue = ADT (실제로 구현을 설명하진 않고 개념적인 것만 설명)

Heap : data structure(실제로 구현), Priority queue의 구현체

프로세스 스케줄링 : ready queue(Priority Queue)로 구현할 수 있음

• 우선순위가 높은 프로세스를 준비상태에서 실행상태로 변경

heap sort(힙 정렬) : 힙에 넣어두고 delete 해도 정렬되어서 결과를 받음

heap 메모리 : heap과는 관련이 없음,

• heap 메모리의 heap은 사전적 의미로 더미(메모리에 쌓여있는 더미)