dev-waterparsley

01. 우선순위 큐

▪️ 큐: 먼저 들어간 데이터가 먼저 삭제되는 자료구조, 먼저 줄을 선 사람이 먼저 서비스를 받는 구조

▪️(힢을 이용한) 우선순위 큐: 대기 리스트에서 항상 우선순위가 높은 사람이 먼저 서비스를 받는 구조

🔸우선순위 큐의 배열 구현

• 데이터 삽입(Add_q()): 삽입 시, 우선순위를 고려하지 않고 순서대로 삽입

• 데이터 삭제(Delete_q()): 삭제 시, 우선순위 고려하여 삭제
  • Delete_q()에 의해 큐의 front 포인터에 있던 1이 삭제되면서 나머지 데이터 중에서 가장 작은 값인 2가 다음 삭제 위치(front가 가리키는 위치)로 이동됨

▪️ 우선순위 큐의 작동 방식

1. 삭제 명령이 실행되면 저장된 데이터 중에서 우선 순위가 가장 높은/낮은 데이터가 삭제됨
   • 10000건의 데이터가 있다고 가정했을 때 우선 순위대로 삭제 연산을 실행할 경우 9999번의 비교 필요 => 오버헤드 발생
   • 이를 해결하기 위해 자료구조 힢을 만듬 == 우선순위 큐를 구현하기 위해 힢을 고안
2. 나머지 데이터들은 어떤 순서로 저장되는 문제되지 않음

02. 힢

✅힢

• 피라미드 모양으로 쌓아 올린 더미이고 항상 맨 위에 있는 것을 먼저 꺼내는 구조
• 힢 추상 자료형
  • 힢 객체의 정의: 부모-자식 노드사이에서 부분적으로 정렬된 완전 이진트리로 부모노드는 자식노드보다 우선순위가 높음
  • 연산
    1. insert(element)::=힢에 데이터 삽입
    2. remove()::=힢(루트)에서 데이터 삭제
    3. peek()::=힢(루트)에서 데이터 읽어오기
    4. isEmpty()::=힢이 비었는지 확인
    5. size()::=힢에 저장한 데이터 개수 확인

🔸힢의 종류

① 최소 힢: 루트가 전체 노드 중에서 최소값을 가짐

• 트리의 모든 노드가 자식 노드보다 작은 값을 가짐(루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐)
• 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
• 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음(=형제 노드 사이에서 크기 제한 없음)

② 최대 힢: 루트가 전체 노드 중에 최대값을 가짐

• 트리의 모든 노드가 자식 노드보다 큰 값을 가짐(루트가 가장 큰 값을 갖고 부모는 자식보다 큰 값을 가지면 됨)
• 트리의 레벨에 따라 데이터가 순서를 갖지는 않음
• 탐색 트리처럼 왼쪽 노드와 오른족 노드 사이에 크기 제한도 없음

🔸힢이 아닌 경우

03. 힢 노드의 삭제 및 삽입

🔸힢 구현을 위한 자료구조

• 배열을 이용한 힢의 구현: 완전 이진트리이기 때문에 배열로 구현해도 기억장소 낭비가 없음
  • 연결 리스트보다 실행 속도 면에서 효율적임
  • 기억장소 측면에서도 장점을 가짐 → 포인터 부분에 대한 영역을 따로 관리하지 않으니까

🔸힢의 노드 삭제

== 우선순위 큐에서 front가 가리키는 데이터를 삭제 == 힢에서는 루트 노드

🔸힢의 노드 삽입

• 데이터 삽입 후 확인해야할 것
  • 완전 이진 트리가 맞는가? YES
  • 부모와 자식 간의 관계가 다른 노들과 같은가? NO => 데이터 교환