[C++] 6월 2일 코딩 테스트 수업

heap을 vector로 구현
힙인데 위아래 조절 가능, 전역함수 포인터로 부등호 연산자, heap인데 사이즈 조절 가능  -> 갱신 힙을 만들기 위한 초반 작업

#pragma once

#include <stdio.h>
#include <vector>

class C_HEAP
{
private:
	struct S_NODE
	{
		int nData;

	};

	std::vector<S_NODE*> m_vBuffer;
	bool (*m_pCompare)(S_NODE*&, S_NODE*&);

private:
	static bool force(S_NODE*& pDst, S_NODE*& pSrc);

	void swap(int nDst, int nSrc);
	void moveUp(int nDst, bool (*pFunc)(S_NODE*&, S_NODE*&));
	void moveDown(int nDst, bool (*pFunc)(S_NODE*&, S_NODE*&));


public:
	static bool less(S_NODE*& pDst, S_NODE*& pSrc);
	static bool greater(S_NODE*& pDst, S_NODE*& pSrc);

public:
	C_HEAP() = default;
	void init(int nBufferSize = 50, bool (*pFunc)(S_NODE*&, S_NODE*&) = less);
	void add(int nData);
	void print();
	S_NODE* top();
	S_NODE* pop();
};

 

#include "heap.h"

bool C_HEAP::less(S_NODE*& pDst, S_NODE*& pSrc)
{
	return pDst->nData < pSrc->nData;
}

bool C_HEAP::greater(S_NODE*& pDst, S_NODE*& pSrc)
{
	return pDst->nData > pSrc->nData;
}

bool C_HEAP::force(S_NODE*& pDst, S_NODE*& pSrc)
{
	return true;
}

void C_HEAP::swap(int nDst, int nSrc)
{
	S_NODE* pTmp = m_vBuffer[nDst];
	m_vBuffer[nDst] = m_vBuffer[nSrc];
	m_vBuffer[nSrc] = pTmp;
}

void C_HEAP::moveUp(int nDst, bool (*pFunc)(S_NODE*&, S_NODE*&))
{
	int nUp = nDst / 2;
	if (nUp == 0)
		return;

	if (pFunc(m_vBuffer[nDst], m_vBuffer[nUp]))
	{
		swap(nDst, nUp);
		moveUp(nUp, pFunc);
	}
}

void C_HEAP::moveDown(int nDst, bool(*pFunc)(S_NODE*&, S_NODE*&))
{
	int nL = nDst * 2;
	int nR = nL + 1;

	if (nL >= m_vBuffer.size())
		return;

	int nSelect = nL;

	if (nR <= m_vBuffer.size() && !pFunc(m_vBuffer[nL], m_vBuffer[nR]))
		nSelect = nR;

	if (pFunc(m_vBuffer[nSelect], m_vBuffer[nDst]));
	{
		swap(nSelect, nDst);
		moveDown(nSelect, pFunc);
	}
}

void C_HEAP::init(int nBufferSize, bool (*pFunc)(S_NODE*&, S_NODE*&))
{
	m_pCompare = pFunc;
	m_vBuffer.reserve(nBufferSize);
	m_vBuffer.push_back(nullptr);
}

void C_HEAP::add(int nData)
{
	if (m_vBuffer.size() == m_vBuffer.capacity())
		return;

	S_NODE* pNode = new S_NODE{};
	pNode->nData = nData;

	m_vBuffer.push_back(pNode);
	int nId = m_vBuffer.size() - 1; // 이거 1 집어넣으면 2나올꺼임 그래서 -1한거 

	// 위로 올린다.

	moveUp((int)m_vBuffer.size() - 1, m_pCompare);


}

void C_HEAP::print()
{
	for (int i = 1; i < m_vBuffer.size(); i++)
	{
		printf("%d ", m_vBuffer[i]->nData);
	}
	printf("\n");
}

C_HEAP::S_NODE* C_HEAP::top()
{
	if (m_vBuffer.size() <= 1)
		return nullptr;

	return m_vBuffer[1];
}

C_HEAP::S_NODE* C_HEAP::pop()
{
	if (m_vBuffer.size() <= 1)
		return nullptr;

	int nLast = (int)m_vBuffer.size() - 1;

	swap(nLast, 1);
	delete m_vBuffer[nLast];
	m_vBuffer.pop_back();

	moveDown(1, m_pCompare);

}

#include <iostream>
#include "heap.h"

int main()
{
	C_HEAP cHeap{};

	cHeap.init(50, C_HEAP::less);
	cHeap.add(7);
	cHeap.add(5);
	cHeap.add(8);
	cHeap.add(3);
	cHeap.add(2);
	cHeap.add(1);

	cHeap.print();

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