우선순위 큐 - 삽입, 삭제 함수

우선순위 큐

• 우선순위를 가진 데이터를 저장하는 큐
• 우선순위가 높은 데이터가 가장 먼저 나옴
• 운영체제 작업 스케줄링, 정렬, 네트워킹 관리 등에 적용
• 전체트리가 최대 힙 구조(max heap, 부모 노드가 자식 노드보다 값이 큰 완전이진트리)를 유지해야
  ​
  ​
  ​

큐와 우선순위큐의 차이

• 큐는 선형적 형태
• 우선순위 큐는 트리 구조로 보는 것이 합리적
• 완전 이진트리를 이용해 구현
  ​
  ​
  ​

우선순위 큐의 삽입(push)

• 삽입 후 루트까지 거슬러 올라가면서 정렬(상향식)

• logN 시간 소요
  ​

  typedef struct {
  int heap[MAX_SIZE];
  int count;
  }priorityQueue;
  ​
  void    push(priorityQueue *pq, int data)
  {
    if (pq->count >= MAX_SIZE)
      return;
    pq->heap[pq->count] = data;
  
    int now, parent;
    now = pq->count;
    parent = (pq->count - 1) / 2;
    while (now > 0 && pq->heap[now] > pq->heap[parent])
    {
      swap(&pq->heap[now], &pq->heap[parent]);
      now = parent;
      parent = (parent - 1) / 2;
    }
    pq->count++;
  }

  ​
  ​
  ​

우선순위큐의 삭제(pop)

• 루트노드를 삭제하고 가장 마지막 원소를 루트 노드의 위치로 옮김

• 삭제 이후 리프 노드까지 내려가면서 최대 힙을 구성(하향식)
  ​

  int    pop(priorityQueue *pq)
  {
    if (pq->count <= 0)
      return -9999;
    int res = pq->heap[0];
    pq->count--;
    pq->heap[0] = pq->heap[pq->count];
    int now = 0, leftChild = 1, rightChild = 2;
    int target = now;
    while (leftChild < pq->count)
    {
      if (pq->heap[target] < pq->heap[leftChild])
        target = leftChild;
      if (pq->heap[target] < pq->heap[rightChild] && rightChild < pq->count)
        target = rightChild;
      if (target == now)
        break;
      else
      {
        swap(&pq->heap[now], &pq->heap[target]);
        now = target;
        leftChild = now * 2 + 1;
        rightChild = now * 2 + 2;
      }
    return res;
  }

  ​