우선순위 큐 & 힙(Priority Queue & Heap)

• 힙(Heap)

힙은 데이터에서 최대값(혹은 최소값을) 빠르게 찾을 수 있는 자료구조

힙은 완전 이진 트리다.

우선순위가 가장 높은 데이터가 제일 앞(루트)에 위치한다.

부모는 자식보다 우선순위가 더 높은 데이터가 배치된다.
(ex. 큰 데이터가 더 우선된다면, 모든 부모 노드는 자신의 자식 노드보다 더 크다)

대표적으로 최대 힙과 최소 힙이 있다.

최대 힙(Max Heap) : 
데이터 중 가장 큰 값이 루트에 위치

모든 부모 노드는 자식보다 크거나 같다.

최소 힙(Min Heap) :

데이터 중 가장 작은 값이 루트에 위치

모든 부모 노드는 자식보다 작거나 같다.

• 배열을 활용한 힙 구현

• 우선순위 큐(Priority Queue)

데이터들이 우선순위를 갖는다.

입력순서에는 상관없이 우선순위가 높은 데이터가 가장 먼저 처리된다.

아래의 모든 설명은 최대 힙을 활용한 우선순위 큐이다.

• 삽입

//삽입

void Heap::Insert(int data)

{

        //힙이 가득 찼는지 확인

        if (IsFull())

               return;

 

        //가장 뒷쪽에 데이터 삽입

        m_Heap[m_Last] = data;

                             

        //처음 삽입된 데이터가 아니라면, 업힙 수행

        if (IsEmpty() == false)

               UpHeap(m_Last);

 

        //last를 뒤로 한칸 밀어냄

        m_Last++;

}

 

//데이터를 위로 밀어냄

void Heap::UpHeap(int index)

{

        //현재 데이터의 부모 데이터

        int parent = PARENT(index);

 

        //최대 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        while (m_Heap[parent] < m_Heap[index])

        {

               //부모와 자신의 위치 교환

               SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

               index = parent;                           //위치

 

               //현재 위치에서 부모 위치 계산                                                               

               parent = PARENT(index);

        }

 

 

        //최소 힙

        //자신보다 더 작은 부모를 찾을때까지 반복

        //while (m_Heap[parent] > m_Heap[index])

        //{

        //      //부모와 자신의 위치 교환

        //      SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

        //      index = parent;                           //위치

 

        //      //현재 위치에서 부모 위치 계산

        //      parent = PARENT(index);

        //}

}

• 삭제
  

//출력(혹은 삭제)

int Heap::Get(void)

{

        //힙이 비었으면 수행 안함

        if (IsEmpty())

               return -999999;

 

        //리턴할 데이터 저장, ROOT = 0 <= 즉, 첫번째 데이터

        int data = m_Heap[ROOT];

              

        //가장 마지막에 위치함 데이터를 첫번째 위치로 이동

        m_Heap[ROOT] = m_Heap[--m_Last];

 

        //다운 힙 수행

        DownHeap(ROOT);

 

        return data;

}

 

//데이터를 아래로 밀어냄

void Heap::DownHeap(int index)

{

        //위치를 교환할 자식의 위치

        int child = 0;

 

        //왼쪽 자식

        int left = LEFT(index);

 

        //오른쪽 자식의 위치

        int right = RIGHT(index);

 

        //최대 힙

        while (left < m_Last)

        {

 

               //오른쪽 자식이 있다면, 좌우 자식을 비교해 큰 자식을 고름

               if (right < m_Last)

                       child = m_Heap[left] > m_Heap[right] ? left : right;

               else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

                       child = left;

 

               //자식들 중 큰 수와 비교해, 밀어내릴 대상이 더 크다면 반복 종료

               if (m_Heap[index] >= m_Heap[child])

                       break;

 

               //자식과 대상을 교환

               SWAP(int, m_Heap[index], m_Heap[child]);

 

               //자식의 위치를 현재 위치로

               index = child;

 

               left = LEFT(index);             //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

        }

 

 

        //최소 힙

        //while (left < m_Last)

        //{

        //      //오른쪽 자식이 있다면, 좌우 자식을 비교해 작은 자식을 고름

        //      if (right < m_Last)

        //             child = m_Heap[left] < m_Heap[right] ? left : right;

        //      else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

        //             child = left;

 

        //      //자식들 중 작은 수와 비교해, 밀어내릴 대상이 더 작다면 반복 종료

        //      if (m_Heap[index] <= m_Heap[child])

        //             break;

 

        //      //자식과 대상을 교환

        //      SWAP(int, m_Heap[index], m_Heap[child]);

 

        //      //자식의 위치를 현재 위치로

        //      index = child;

 

        //      left = LEFT(index);             //왼쪽 자식 위치

        //      right = RIGHT(index);   //오른쪽 자식 위치

        //}

}

• 전체 코드

#pragma once

 

//매크로 함수들

#define ROOT 0

#define PARENT(n) (n-1)/2  //부모 위치

#define LEFT(n) 2*n + 1    //왼쪽 자식 위치

#define RIGHT(n) 2*n + 2   //오른쪽 자식 위치

//교환

#define SWAP(type, a, b) do{ \

    type temp = a;      \

    a = b;                     \

    b = temp;           \

}while(false)

 

class Heap

{

public:

        Heap();

        Heap(int size);

        ~Heap();

 

private:

        int *m_Heap;            //데이터들 저장할 공간

        int m_Last;             //현재 마지막 자료의 위치 + 1(빈 위치)

        int m_Size;             //최대 사이즈

 

public:

        bool IsEmpty(void);     //힙이 비었는지 확인

        bool IsFull(void);      //힙이 가득 찼는지 확인

        void Insert(int);       //삽입

        int  Get(void);         //데이터 수령

        void Print(void);       //프린트

 

        void Resize(int size);   //배열 크기 다시설정

        void Clear();            //다시 사용가능한 상태로

        void Reset();            //다시 사용가능한 상태로

private:

        void UpHeap(int);        //업힙 : 데이터를 위로 밀어냄

        void DownHeap(int);      //다운힙 : 데이터를 아래로 밀어냄

        void SetSize(int size);  //사이즈 지정

};

#include "stdafx.h"

#include "Heap.h"

 

 

Heap::Heap()

{

        Reset();

 

        SetSize(10);

}

 

Heap::Heap(int size)

{

        Reset();

 

        SetSize(size);

}

 

 

Heap::~Heap()

{

        Clear();

}

 

//힙이 비었는지 확인

bool Heap::IsEmpty(void)

{

        //last가 0이면 데이터가 없음

        if (m_Last == 0)

               return true;

        else

               return false;

}

 

//힙이 가득 찼는지 확인

bool Heap::IsFull(void)

{

        //last와 최대크기가 같으면, 가득찬 것

        if (m_Last == m_Size)

               return true;

        else

               return false;

}

 

//삽입

void Heap::Insert(int data)

{

        //힙이 가득 찼는지 확인

        if (IsFull())

               return;

 

        //가장 뒷쪽에 데이터 삽입

        m_Heap[m_Last] = data;

 

        //처음 삽입된 데이터가 아니라면, 업힙 수행

        if (IsEmpty() == false)

               UpHeap(m_Last);

 

        //last를 뒤로 한칸 밀어냄

        m_Last++;

}

 

//데이터 수령

int Heap::Get(void)

{

        //힙이 비었으면 수행 안함

        if (IsEmpty())

               return -999999;

 

        //리턴할 데이터 저장, ROOT = 0 <= 즉, 첫번째 데이터

        int data = m_Heap[ROOT];

 

        //가장 마지막에 위치함 데이터를 첫번째 위치로 이동

        m_Heap[ROOT] = m_Heap[--m_Last];

 

        //다운 힙 수행

        DownHeap(ROOT);

 

        return data;

}

 

//데이터를 위로 밀어냄

void Heap::UpHeap(int index)

{

        //현재 데이터의 부모 데이터

        int parent = PARENT(index);

 

        //최대 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        while (m_Heap[parent] < m_Heap[index])

        {

               //부모와 자신의 위치 교환

               SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

               index = parent;                                                       //위치

 

                                                                                                   //현재 위치에서 부모 위치 계산                                                               

               parent = PARENT(index);

        }

 

 

        //최소 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        //while (m_Heap[parent] > m_Heap[index])

        //{

        //      //부모와 자신의 위치 교환

        //      SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

        //      index = parent;                                                       //위치

 

        //                                                                                          //현재 위치에서 부모 위치 계산                                                               

        //      parent = PARENT(index);

        //}

}

 

//데이터를 아래로 밀어냄

void Heap::DownHeap(int index)

{

        //위치를 교환할 자식의 위치

        int child = 0;

 

        //왼쪽 자식

        int left = LEFT(index);

 

        //오른쪽 자식의 위치

        int right = RIGHT(index);

 

        //최대 힙

        while (left < m_Last)

        {

               //left = LEFT(index);           //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

 

                                                             //오른쪽 자식이 있다면, 좌우 자식을 비교해 큰 자식을 고름

               if (right < m_Last)

                       child = m_Heap[left] > m_Heap[right] ? left : right;

               else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

                       child = left;

 

               //자식들 중 큰 수와 비교해, 밀어내릴 대상이 더 크다면 반복 종료

               if (m_Heap[index] >= m_Heap[child])

                       break;

 

               //자식과 대상을 교환

               SWAP(int, m_Heap[index], m_Heap[child]);

 

               //자식의 위치를 현재 위치로

               index = child;

 

               left = LEFT(index);             //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

        }

 

 

        //최소 힙

        //while (left < m_Last)

        //{

        //      //오른쪽 자식이 있다면, 좌우 자식을 비교해 작은 자식을 고름

        //      if (right < m_Last)

        //             child = m_Heap[left] < m_Heap[right] ? left : right;

        //      else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

        //             child = left;

 

        //      //자식들 중 작은 수와 비교해, 밀어내릴 대상이 더 작다면 반복 종료

        //      if (m_Heap[index] <= m_Heap[child])

        //             break;

 

        //      //자식과 대상을 교환

        //      SWAP(int, m_Heap[index], m_Heap[child]);

 

        //      //자식의 위치를 현재 위치로

        //      index = child;

 

        //      left = LEFT(index);             //왼쪽 자식 위치

        //      right = RIGHT(index);   //오른쪽 자식 위치

        //}

}

 

void Heap::Print(void)

{

        for (int i = 0; i < m_Last; i++)

               printf("%d ", m_Heap[i]);

 

        printf("\n");

}

 

// 배열 크기 다시설정

void Heap::Resize(int size)

{

        Clear();

 

        SetSize(size);

 

        Reset();

}

 

//데이터 삭제

void Heap::Clear()

{

        delete[] m_Heap;

        m_Heap = NULL;

}

 

//다시 사용가능한 상태로

void Heap::Reset()

{

        m_Last = 0;

}

 

//배열 크기 지정

void Heap::SetSize(int size)

{

        m_Size = size;

        m_Heap = new int[m_Size];

}