[강의] 11월 28일 수업정리

오늘은 heap구조에 대한 수업을 들었다.

 

1. HEAP 구조

1. HEAP 구조란

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙은 일종의 반정령 상태를 유지하며 큰 ㄱ밧이 상위 레밸에 있고 작은 값이 하위 레밸에 있다는 정도이며 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.

힙 트리에서는 중복된 값을 허용한다 ( 일반 적인 이진 탐색 트리에서는 중복된 값을 허용하지 않음. )

 

1.2 HEAP 구조 예시

// heap.h
#pragma once

#include <stdio.h>

class C_HEAP
{
private:
	int m_arData[11];
	int m_nLastIndex;

private:
	void swap(int& nDst, int& nSrc);

public:
	C_HEAP() = default;
	bool add(const int& nData);
	bool top(int& nData);
	void pop();
	void print();
};

// heap.cpp
#include "heap.h"

void C_HEAP::swap(int& nDst, int& nSrc)
{
    int nTmp = nDst;
    nDst = nSrc;
    nSrc = nTmp;
}


bool C_HEAP::add(const int& nData)
{
    if (m_nLastIndex + 1 == 11)
        return false;

    m_nLastIndex++;
    m_arData[m_nLastIndex] = nData;

    int nCurrent = m_nLastIndex;
    int nParent = nCurrent / 2;

    while (nParent != 0 && m_arData[nParent] > m_arData[nCurrent])
    {
        swap(m_arData[nParent], m_arData[nCurrent]);

        nCurrent = nParent;
        nParent = nCurrent / 2;
    }

    return true;
}

bool C_HEAP::top(int& nData)
{


    return false;
}

void C_HEAP::pop()
{
}

void C_HEAP::print()
{
    for (int i = 1; i <= m_nLastIndex; i++)
    {
        printf("%d ", m_arData[i]);
    }
    printf("\n");
}

// main.cpp
#include <iostream>
#include "heap.h"

int main()
{
	C_HEAP cHeap{};

	cHeap.add(5);
	cHeap.add(2);
	cHeap.add(7);
	cHeap.add(6);
	cHeap.add(9);
	cHeap.add(8);
	cHeap.add(1);
	cHeap.add(3);
	cHeap.add(4);
	cHeap.add(0);

	cHeap.print();
}

 

 

1.3 HEAP 구조 재귀 함수

// heap.h
#pragma once

#include <stdio.h>

class C_HEAP
{
private:
	int m_arData[11];
	int m_nLastIndex;

private:
	void swap(int& nDst, int& nSrc);
	void up(int nCurrent, int nParent);

public:
	C_HEAP() = default;
	bool add(const int& nData);
	bool top(int& nData);
	void pop();
	void print();
};

// hearp.cpp
#include "heap.h"

void C_HEAP::swap(int& nDst, int& nSrc)
{
    int nTmp = nDst;
    nDst = nSrc;
    nSrc = nTmp;
}

void C_HEAP::up(int nCurrent, int nParent)
{
    if (nParent == 0 || m_arData[nCurrent] >= m_arData[nParent])
        return;

    swap(m_arData[nCurrent], m_arData[nParent]);
    up(nParent, nParent / 2);
}

bool C_HEAP::add(const int& nData)
{
    if (m_nLastIndex + 1 == 11)
        return false;

    m_nLastIndex++;
    m_arData[m_nLastIndex] = nData;

    up(m_nLastIndex, m_nLastIndex / 2);

    return true;
}

bool C_HEAP::top(int& nData)
{


    return false;
}

void C_HEAP::pop()
{
}

void C_HEAP::print()
{
    for (int i = 1; i <= m_nLastIndex; i++)
    {
        printf("%d ", m_arData[i]);
    }
    printf("\n");
}

// main.cpp

int main()
{
	C_HEAP cHeap{};

	cHeap.add(5);
	cHeap.add(2);
	cHeap.add(7);
	cHeap.add(6);
	cHeap.add(9);
	cHeap.add(8);
	cHeap.add(1);
	cHeap.add(3);
	cHeap.add(4);
	cHeap.add(0);

	cHeap.print();
}

 

1.4 [ 과제 ] HEAP 알고리즘 

//heap.h
#pragma once

#include <stdio.h>

class C_HEAP
{
private:
	int m_arData[11];
	int m_nLastIndex;

private:
	void swap(int& nDst, int& nSrc);
	void up(int nCurrent, int nParent);

public:
	C_HEAP() = default;
	bool add(const int& nData);
	bool top(int& nData);
	void pop();
	void print();
};

//heap.cpp
#include "heap.h"

void C_HEAP::swap(int& nDst, int& nSrc)
{
    int nTmp = nDst;
    nDst = nSrc;
    nSrc = nTmp;
}

void C_HEAP::up(int nCurrent, int nParent)
{
    if (nParent == 0 || m_arData[nCurrent] >= m_arData[nParent])
        return;

    swap(m_arData[nCurrent], m_arData[nParent]);
    up(nParent, nParent / 2);
}

bool C_HEAP::add(const int& nData)
{
    if (m_nLastIndex + 1 == 11)
        return false;

    m_nLastIndex++;
    m_arData[m_nLastIndex] = nData;

    up(m_nLastIndex, m_nLastIndex / 2);

    return true;
}

bool C_HEAP::top(int& nData)
{
    if (m_arData[m_nLastIndex = 0])
        return false;

    nData = m_arData[1];
    return true;
}

void C_HEAP::pop()
{
    if (m_nLastIndex == 0)
        return;

    m_arData[1] = m_arData[m_nLastIndex];
    m_nLastIndex--;

    int nCurrent = 1;
    int nLeft = nCurrent * 2;
    int nRight = nLeft + 1;

    while (nLeft <= m_nLastIndex) 
    {
        int nMin = nCurrent; 

        if (m_arData[nLeft] < m_arData[nMin])
        {
            nMin = nLeft;
        }

        if (nRight <= m_nLastIndex && m_arData[nRight] < m_arData[nMin])
        {
            nMin = nRight;
        }

        if (nMin == nCurrent)
        {
            nLeft = m_nLastIndex + 1; 
        }
        else
        {
            swap(m_arData[nCurrent], m_arData[nMin]);
            nCurrent = nMin;
            nLeft = nCurrent * 2;
            nRight = nLeft + 1;
        }
    }
}

void C_HEAP::print()
{
    for (int i = 1; i <= m_nLastIndex; i++)
    {
        printf("%d ", m_arData[i]);
    }
    printf("\n");
}

//main.cpp
#include <iostream>
#include "heap.h"

int main()
{
	C_HEAP cHeap{};

	cHeap.add(5);
	cHeap.add(2);
	cHeap.add(7);
	cHeap.add(6);
	cHeap.add(9);
	cHeap.add(8);
	cHeap.add(1);
	cHeap.add(3);
	cHeap.add(4);
	cHeap.add(0);

	cHeap.print();
	cHeap.pop();

	cHeap.print();
}