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

Priority queue(우선순위 큐)

• 큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨.

 

우선순위 큐 주요 동작

• insert
  • 아이템을 넣어주는 것. 아이템의 우선순위정보도 같이 넣어줘야함.
• delete
  • 큐에서 우선순위가 높은 아이템을 뺴는 것
• peek
  • delete와 비슷하지만 우선순위 큐에서 제거는 하지 않는 동작

 

우선순위 큐 동작 방식

• 큐 안에 10, 20, 5 아이템들을 순차적으로 집어 넣는다.
• delete를 호출하면 우선순위가 높은 20을 빼내게 된다.
• delete를 호출하면 우선순위가 높은 10을 빼내게 된다.
• delete를 호출하면 마지막으로 남은 5을 빼내게 된다.

힙은 주로 이진트리 기반으로 구현된다.

 

힙은 max heap과 min heap이 있다.

 

max heap

• 부모 노드의 키가 자식 노드의 키보다 크거나 같은 트리

min heap

• 부모 노드의 키가 자식 노드의 키보다 작거나 같은 트리

 

힙 주요 동작

• insert
  • 아이템을 집어넣는것인데 이때 키값도 같이 넣어줘야함.
• delete
  • max heap이면 키값이 가장 큰 아이템을 빼고,  min heap이면 가장 작은 아이템을 뺸다.
• peek
  • delete랑 같지만 실제로는 꺼내지 않는다.

 

 

 

 

Priority queue와 Heap의 관계

• 힙의 키를 우선순위로 사용한다면 힙은 우선순위 큐의 구현체가 된다.
• heap은 데이터 구조이고, Priority queue ADT(개념)

 

우선순위 큐와 힙의 사용 사례

• 프로세스 스케줄링
• heap sort(힙 정렬)
• 힙 메모리는 지금 배운 힙과 관련이 없다.