Ch09. 우선순위 큐(Priority Queue)와 힙(Heap)

34269 단어 자료구조자료구조

09-1. 우선순위 큐의 이해

우선순위가 높은 데이터가 먼저 나온다
데이터를 근거로 우선순위를 판단할 수 있어야 한다

우선순위 큐의 구현 방법

  • 배열을 기반으로 구현하는 방법
  • 연결 리스트를 기반으로 구현하는 방법
  • 힙을 이용하는 방법

힙(Heap)의 소개

힙 : 완전 이진 트리. 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같아 루트 노드가 가장 큰 값을 저장하는 트리.
heap : 무엇인가를 차곡차곡 쌓아 올린 더미

  • 최대힙 : 루트 노드가 올라갈수록 저장된 값이 커지는 완전 이진트리
  • 최소힙 : 루트 노드가 올라갈수록 저장된 값이 작아지는 완전 이진 트리

09-2. 힙의 구현과 우선순위 큐의 완성

힙에서의 데이터 저장과정

자식 노드 데이터의 우선순위 <= 부모 노드 데이터의 우선순위

힙에서의 데이터 삭제과정

마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다

삽입과 삭제의 과정에서 보인 성능의 평가

  • 배열
    • 데이터 저장의 시간 복잡도 : O(n)
    • 데이터 삭제의 시간 복잡도 : O(1)
  • 연결 리스트
    • 데이터 저장의 시간 복잡도 : O(n)
    • 데이터 삭제의 시간 복잡도 : O(1)
  • 힙
    • 데이터 저장의 시간 복잡도 : O(log2(n))
    • 데이터 삭제의 시간 복잡도 : O(log2(n))

힙을 이용하면 트리의 높이에 해당하는 수만큼만 연산을 하면 된다

힙의 구현에 어울리는 것은 연결리스트? 아니면 배열?

배열을 기반으로 한다.

연결리스트를 기반으로 구현하면, 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다

배열을 기반으로 힙을 구현하는데 필요한 지식들

노드에 고유한 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다

  • 왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 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

원리 이해 중심의 힙 구현 : HDelete 함수에 대한 설명 중심으로

  • 힙은 완전 이진 트리이다.
  • 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.
  • 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.
  • 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.
  • 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정한다.

#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;
}

GetHiPriChildIDX : 두 자식 노드 중에서 우선순위가 높은 것의 인덱스 값을 반환한다.
자식 노드가 없으면 0을 반환하고 하나인 경우에는 그 노드의 인덱스 값을 반환한다.

하나뿐인 자식노드는 왼쪽 자식 노드이고, 힙의 마지막 노드이다.

HDelete : 힙의 마지막 노드를 루트 노드의 위치에 옮긴 다음에, 자식 노드와의 비교 과정을 거치면서 아래로 내린다. 자신의 위치를 찾을 때까지 내린다.

원리 이해 중심의 힙 구현 : HInsert 함수에 대한 설명 중심으로

HInsert : 새로운 데이터는 우선 순위가 가장 낮다는 가정 하에서 마지막 위치에 저장한다. 우선순위의 비교를 통해서 자신의 위치를 찾을 때까지 위로 올린다.

제법 쓸만한 수준의 힙 구현 : 힙의 변경

프로그래머가 우선순위의 판단 기준을 힙에 설정할 수 있어야 한다.

typedef struct _heap
{
    PriorityComp *comp;
    int numOfData;
    HData heapArr[HEAP_LEN];
} Heap;

PriorityComp
typedef int PriorityComp(HData d1, HData d2);

  • 첫 번째 인자의 우선순위가 높다면, 0보다 큰 값이 반환되도록 정의한다
  • 두 번째 인자의 우선순위가 높다면, 0보다 작은 값이 반환되도록 정의한다
  • 첫 번째, 두 번째 인자의 우선순위가 동일하다면, 0이 반환되도록 정의한다

제법 쓸만한 수준의 힙 구현 : 힙의 변경사항 완성하기

변경해야 하는 함수

  • int GetHiPriChildIDX(Heap *ph, int idx);
  • void HInsert(Heap *ph, HData data);
  • HData HDelete(Heap *ph);

GetHiPriChildIDX

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->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)] < 0)
            return GetRChildIDX(idx);
        else
            return GetLChildIDX(idx);
    }
}

HInsert

void HInsert(Heap *ph, HData data)
{
    int idx = ph->numOfData+1;
    
    where(idx != 1)
    {
        if(ph->comp(data, ph->heapArr[GetParentIDX(idx)] > 0)
        {
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
            idx = GetParentIDX(idx);
        }
        else
        {
            break;
        }
    }
    
    ph->heapArr[idx] = data;
    ph->numOfData += 1;
}

HDelete

HData HDelete(Heap *ph)
{
    HData retData = ph->heapArr[1];
    HData lastElem = ph->heapArr[ph->numOfData];
    
    int parentIdx = 1;
    int childIdx;
    
    while(childIdx = GetHiPriChildIDX(ph, parentIdx))
    {
        if(ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)
            break;
        
        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx;
    }
    
    ph->heapArr[parentIdx] = lastElem;
    ph->numOfData -= 1;
    return retData;
}

제법 쓸만한 수준의 힙을 이용한 우선순위 큐의 구현

우선순위 큐 자료구조의 ADT

  • void PQueueInit(PQueue *ppq, PriorityComp pc);
    • 우선순위 큐의 초기화를 진행한다
    • 우선순위 큐 생성 후 제일 먼저 호출되어야 하는 함수이다
  • int PQIsEMpty(PQueue *ppq);
    • 우선순위 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다
  • void PEnqueue(PQueue *ppq, *PQData data);
    • 우선순위 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.
  • PQData PDequeue(PQueue *ppq);
    • 우선순위가 가장 높은 데이터를 삭제한다
    • 삭제된 데이터는 반환된다
    • 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다
#ifndef __PRIORITY_QUEUE_H__
#define __PRIORITY_QUEUE_H__

#include "UsefulHeap.h"

typedef Heap PQueue;
typedef HData PQData;

void PQueueInit(PQueue *ppq, PriorityComp pc);
int PQIsEmpty(PQueue *ppq);

void PEnqueue(PQueue * ppq, PQData data);
PQData PDequeue(PQueue *ppq);

#endif
#include "PriorityQueue.h"
#include "UsefulHeap.h"

void PQueueInit(PQueue *ppq, PriorityComp pc)
{
    HeapInit(ppq, pc);
}

int PQIsEmpty(PQueue *ppq)
{
    return HIsEmpty(ppq);
}

void PEnqueue(PQueue *ppq, PQData data)
{
    HInsert(ppq, data);
}

PQData PDenqueue(PQueue *ppq)
{
    return HDelete(ppq);
}
[BOJ] - 10430
Django Framework - Release

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage