山のような小さなヒープを実現します.

2204 ワード

データ構造二叉の木——再帰と非再帰

擬似関数とは、クラスの使用を関数のように見えることです.その実現はクラスの中でoperator()を実現して、この種類は類似の関数の行為があって、1つのアナログの関数種類です.
「Test.cpp」

#define _CRT_SECURE_NO_WARNINGS 1
#include 
using namespace std;
#include "Heap.h"

void Test()
{
	int arr[] = {10,16,18,12,11,13,15,17,14,19};
	int size = sizeof(arr)/sizeof(arr[0]);
	Heap> h(arr,size);//  
	//Heap h(arr,size);//  
	h.Cout();

	h.Push(20);
	h.Push(5);
	h.Cout();

	h.Pop();
	h.Pop();
	h.Cout();
}
int main()
{
	Test();
	system("pause");
	return 0;
}

「Heap.h」

#pragma once
#include 
#include 

template
struct Less
{
	bool operator()(const T& left,const T& Right)
	{
		return left < Right;
	}
};

template
struct Greater
{
	bool operator()(const T& left,const T& Right)
	{
		return left > Right;
	}
};

template>//      
class Heap
{
public:
	Heap(const T* arr,const size_t size)
	{
		for (int i = 0;i < size;i++)
		{
			_arr.push_back(arr[i]);
		}

		//  
		for (int i = (_arr.size() - 2) / 2;i >= 0;i--)
		{
			//       ，    ；
			AdjustDown(i);
		}
	}
	void Push(const T& data)
	{
		_arr.push_back(data);
		AdjustUp(_arr.size()-1);
	}
	void Pop()
	{
		assert(_arr.empty() != true);
		swap(_arr[0],_arr[_arr.size()-1]);
		_arr.pop_back();
		AdjustDown(0);
	}
	int Top()
	{
		return _arr[0];
	}
	bool Empty()
	{
		return _arr.empty();
	}
	int Size()
	{
		return _arr.size();
	}
	void Cout()
	{
		for (int i = 0; i < _arr.size();i++)
		{
			cout<<_arr cout="" private:="" void="" adjustdown="" parent="" int="" child="2" compare="" com="" while="" _arr.size="" if="" swap="" else="" break="" adjustup=""> 0)
		{
			if (com(_arr[child],_arr[parent]))
			{
				swap(_arr[child],_arr[parent]);
				child = parent;
				parent = (child - 1) / 2;
			} 
			else
			{
				break;
			}
		}
	}
private:
	vector _arr;
};

線形表-順序表-データ構造java版