자료구조 : 힙(heap)과 우선순위 큐

ROK·2022년 10월 31일
Cheap열혈우선순위 큐자료구조힙
0

열혈 자료구조

목록 보기
26/30

우선순위 큐

우선순위 큐의 이해

이름 그대로 우선순위 큐는 큐와 이름이 같아 같은 걸로 생각할 수 있지만 실제로는 차이가 크다.

큐와 우선순위 큐의 핵심 연산

큐와 우선순위 큐의 핵심 연산은 enqueue(큐/우선순위 큐에 데이터 삽입), dequeue(큐/우선순위 큐에서 데이터 삭제)로 같다.

하지만 연산의 결과에 차이가 있다.

  • 큐
    • 먼저 들어간 데이터가 먼저 나온다.
  • 우선순위 큐
    • 들어간 순서와 관계없이 우선순위가 높은 데이터가 먼저 나온다.

앞서 큐를 줄서기에 비유했다면, 우선순위 큐는 응급실에 비유할 수 있다.
응급실은 환자의 위급한 정도에 따라서 우선순위를 나누고 위급한 환자를 우선적으로 치료한다.

데이터의 우선순위는 프로그래머가 목적에 맞게 우선순위를 결정한다.
예를 들어 정수일 경우에는 수의 크기로 우선순위를 결정할 수 있고, 영단어일 경우 사전적 순서로 우선순위를 결정할 수 있다.

우선순위 큐의 구현

우선순위 큐는 세 가지로 구현할 수 있다

  • 배열을 기반으로 구현
  • 연결 리스트를 기반으로 구현
  • 힙(heap)을 이용한 구현

앞서 계속 사용해온 배열과 연결 리스트는 우선순위 큐를 구현하기는 매우 쉽다.
데이터를 비교해 우선순위가 높은 데이터는 앞으로 낮은 데이터는 뒤로 정렬하면 되기 때문인데, 구현이 쉬운 장점이 성능을 하락하는 주 원인이 된다.

배열과 연결리스트 구현의 단점은 데이터를 삽입, 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀고 당기는 연산을 해야하며, 데이터를 삽입하는 과정에서 저장된 모든 데이터와 우선순위 비교를 진행해야한다.

만약 우선순위가 아주 낮은 데이터라면 거의 모든 데이터와 비교 연산을 진행한다고 볼 수 있다.

이러한 비효율적인 이유로 우선순위 큐는 '힙(heap)'이라는 자료구조를 이용해서 구현하는게 일반적이다.

힙(heap)

힙은 완전 이진 트리 구조를 가지고 있다.

힙의 구조 : '노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다'
(루트 노드의 값이 가장 커야한다)

위 설명에서 값은 '데이터의 값' 또는 '우선순위'이다.

아래 그림과 같이 루트 노드로 갈 수록 저장된 값이 커지는 완전 이진 트리를 최대 힙(max heap)이라고 한다.

아래 그림과 같이 루트 노드로 갈 수록 저장된 값이 작아지는 완전 이진 트리를 최소 힙(min heap)이라고 한다.

힙의 뜻은 차곡차곡 쌓아 올린 더미라는 뜻이 있다.

힙의 구현(1)

힙의 구현은 우선순위 큐의 완성으로 이어진다. 그래서 힙과 우선순위 큐를 동일하게 생각할 수 있지만 우선순위 큐와 힙은 다르다. 이를 구분할 줄 알아야한다.

힙의 구현을 위해 데이터 저장, 삭제 방법을 먼저 알아야한다.
먼저 저장을 살펴보고 이는 최소 힙을 기준으로 한다

힙의 데이터 저장과정

우선 힙의 기본 정의대로 자식 노드 보다는 부모 노드가 우선순위가 높다.

데이터 저장

  • 새로운 데이터는 우선순위가 제일 낮다고 가정하고 *마지막 위치에 저장한다
  • 부모 노드와 우선순위를 비교해서 필요하면 위치를 변경한다.
  • 계속해서 부모노드와 비교해 변경하는 과정 반복한다.
  • 제대로 된 위치를 찾으면 멈춘다.
  • *마지막 위치는 노드를 추가한 이후에도 완전 이진 트리가 유지되는 마지막 레벨의 가장 오른쪽 위치를 의미한다.

위 순서대로 데이터를 추가하는 과정을 살펴본다. 추가하는 데이터는 정수 3

데이터 정수 3을 마지막 위치에 추가하고 부모 노드(13)과 비교한다.
숫자 3이 우선순위가 높기 때문에 위치를 변경하고 다시 부모노드와 비교한다.

3이 부모 노드의 4 보다 우선순위가 높기 때문에 또 변경한다.

최종적으로 위치를 찾아간 모습이다.

힙의 데이터 삭제과정

우선순위 큐의 구현을 위해 힙을 이용하고 있기 때문에 우선순위 큐에서의 삭제를 생각하면, 우선순위 큐에서 데이터 삭제는 우선순위가 가장 높은 데이터 즉, 루트 노드의 삭제를 의미한다.

따라서 루트 노드를 삭제한 이후 그 부분을 어떻게 채울 것인지 고민해야한다.

일반적인 해결책

  • 마지막 노드를 루트 노드의 자리로 옮긴다.
  • 자식 노드와 비교해 올바른 위치를 찾아가도록 한다.


루트 노드가 삭제된 힙



삽입과 삭제에서 성능 평가

우선순위 큐를 구현함에 있어서 힙이 배열과 연결 리스트에 비해 좋은 이유는 무엇인가?

  • 배열

    • 배열 기반 데이터 저장의 시간 복잡도 : O(n)O(n)
    • 배열 기반 데이터 삭제의 시간 복잡도 : O(l)O(l)

  • 연결 리스트

    • 연결 리스트 기반 데이터 저장의 시간 복잡도 : O(n)O(n)
    • 연결 리스트 기반 데이터 삭제의 시간 복잡도 : O(l)O(l)

  • 힙

    • 힙 기반 데이터 저장의 시간 복잡도 : O(log2n)O(log_2n)
    • 힙 기반 데이터 삭제의 시간 복잡도 : O(log2n)O(log_2n)

배열과 연결 리스트의 저장은 저장된 모든 데이터와 우선순위 비교과정을 거치기 때문에 시간 복잡도는 O(n)O(n)가 되고, 삭제는 맨 앞의 데이터만 삭제하면 되기 때문에 O(l)O(l)이 된다.

하지만 힙을 기반으로 하면 저장과 삭제는 부모 자식 노드 사이에서 연산이 일어나기 때문에 트리의 높이에 해당하는 수만큼만 비교 연산을 진행하면 된다.

트리의 높이가 하나 늘어날 때마다 비교연산의 횟수가 하나 증가한다.

힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 증가하면 두 배씩 증가한다. 데이터의 수가 두 배 늘 때마다. 비교연산의 횟수는 1회 증가한다.

힙의 구현(2)

우선순위 큐에 힙을 이용해 구현하는 것은 이야기가 끝났다. 그럼 힙은 어떻게 구현해야할까??
앞서 트리를 구현했던 것처럼 연결 리스트를 이용해 구현하는 것이 좋아보이지만 힙은 배열을 기반으로 구현하는 것이 원칙이다.

그 이유는 새로운 노드를 추가할 때 연결 리스트를 기반으로 구현한다면 마지막 위치에 추가하는 것이 어렵기 때문이다. 배열을 이용한다면 연결 리스트보다 더 간편하게 구현할 수 있다.

배열 기반으로 힙 구현

앞서 트리를 구현할 때 배열을 통해 구현하는 것을 설명한 적이 있다.
배열을 이용해 트리를 구현하면 노드에 고유 번호를 부여하고, 이 고유 번호는 인덱스이다. 그리고 인덱스 0번은 사용하지 않는다.

배열을 활용하기 위해 알아야 하는 것은

  • 자식 노드의 인덱스를 얻는 법
    • 왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 X 2
    • 오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 X 2 + 1
  • 부모 노드의 인덱스를 얻는 법
    • 부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2

여기서 주의할 점은 부모 노드의 인덱스 값을 구한 나눗셈 연산은 정수형 나눗셈이다.

헤더파일

#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__

#define TRUE 1
#define FALSE 0

#define HEAP_LEN 100

typedef char HData;
typedef int Priority;

typedef struct _heapElem
{
   Priority pr;
   HData data;
} HeapElem;

typedef struct _heap
{
   int numOfData;
   HeapElem heapArr[HEAP_LEN];
} Heap;

void HeapInit(Heap *ph);
int HIsEmpty(Heap *ph);

void HInsert(Heap *ph, HData data, Priority pr);
HData HDelete(Heap *ph);

#endif

소스파일

#include "SimpleHeap.h"

void HeapInit(Heap *ph)
{
   ph->numOfData = 0;
}

int HIsEmpty(Heap *ph)
{
   if (ph->numOfData == 0)
   {
      return TRUE;
   }
   else
   {
      return FALSE;
   }
}

int GetParentIDX(int idx)
{
   return idx / 2;
}

int GetLChildIDX(int idx)
{
   return idx * 2;
}

int GetRChildIDX(int idx)
{
   return GetLChildIDX(idx) + 1;
}

int GetHiPriChildIDX(Heap *ph, int idx)
{
   if (GetLChildIDX(idx) > ph->numOfData)
   {
      return 0;
   }
   else if (GetLChildIDX(idx) == ph->numOfData)
   {
      return GetLChildIDX(idx);
   }
   else
   {
      if (ph->heapArr[GetLChildIDX(idx)].pr > ph->heapArr[GetRChildIDX(idx)].pr)
      {
         return GetRChildIDX(idx);
      }
      else
      {
         return GetLChildIDX(idx);
      }
   }
}

void HInsert(Heap *ph, HData data, Priority pr)
{
   int idx = ph->numOfData + 1;
   HeapElem nelem = {pr, data};

   while (idx != 1)
   {
      if (pr < (ph->heapArr[GetParentIDX(idx)].pr))
      {
         ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
         idx = GetParentIDX(idx);
      }
      else
      {
         break;
      }
   }

   ph->heapArr[idx] = nelem;
   ph->numOfData += 1;
}

HData HDelete(Heap *ph)
{
   HData retData = (ph->heapArr[1]).data;
   HeapElem lastElem = ph->heapArr[ph->numOfData];

   int parentIdx = 1;
   int childIdx;

   while (childIdx = GetHiPriChildIDX(ph, parentIdx))
   {
      if (lastElem.pr <= ph->heapArr[childIdx].pr)
      {
         break;
      }
      ph->heapArr[parentIdx] = ph->heapArr[childIdx];
      parentIdx = childIdx;
   }

   ph->heapArr[parentIdx] = lastElem;
   ph->numOfData -= 1;
   return retData;
}

메인파일

#include <stdio.h>
#include "SimpleHeap.h"

int main()
{
   Heap heap;
   HeapInit(&heap);

   HInsert(&heap, 'A', 1);
   HInsert(&heap, 'B', 2);
   HInsert(&heap, 'C', 3);
   printf("%c \n", HDelete(&heap));

   HInsert(&heap, 'A', 1);
   HInsert(&heap, 'B', 2);
   HInsert(&heap, 'C', 3);
   printf("%c \n", HDelete(&heap));

   while (!HIsEmpty(&heap))
   {
      printf("%c \n", HDelete(&heap));
   }

   return 0;
}
profile
ROK
하루에 집중하자
이전 포스트

자료구조 : 수식 트리(Expression Tree) 구현

다음 포스트

자료구조 : 단순 정렬

0개의 댓글