用模板實(shí)現(xiàn)堆

堆數(shù)據(jù)結(jié)構(gòu)是一種數(shù)組對象，它可以被視為一棵完全二叉樹結(jié)構(gòu)。

創(chuàng)新互聯(lián)建站自2013年起，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站制作、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢想脫穎而出為使命，1280元岷縣做網(wǎng)站,已為上家服務(wù),為岷縣各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575

堆結(jié)構(gòu)的二叉樹存儲是

最大堆：每個(gè)父節(jié)點(diǎn)的都大于孩子節(jié)點(diǎn)。

最小堆：每個(gè)父節(jié)點(diǎn)的都小于孩子節(jié)點(diǎn)。

這是一個(gè)普通的堆，我們想把它變成最大堆，就必須了解最大堆的特點(diǎn)。然后我們對它進(jìn)行調(diào)整，保證每個(gè)父節(jié)點(diǎn)的都大于孩子節(jié)點(diǎn)。

我們先調(diào)整這個(gè)二叉樹的一部分，從它的最后一個(gè)節(jié)點(diǎn)開始調(diào)整，圖中紅色箭頭開始調(diào)整，如果父節(jié)點(diǎn)小于孩子節(jié)點(diǎn)，就交換，否則結(jié)束。在看下一個(gè)節(jié)點(diǎn)，一直這樣循環(huán)，直到全部調(diào)整完。

代碼如下：

void _AdjustDown(size_t parent, size_t size)
	{
		size_t child = 2 * parent + 1;
		while (child < size)
		{
			//child + 1 < size保證是最后一個(gè)節(jié)點(diǎn)
			if (child + 1 < size&&_arr[child] < _arr[child + 1])
			{
				child++;//孩子節(jié)點(diǎn)最大的一個(gè)節(jié)點(diǎn)
			}
			//交換
			if (_arr[child]>_arr[parent])
			{
				swap(_arr[child],_arr[parent]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}

如果想把它調(diào)整成最小堆，必須符合每個(gè)父節(jié)點(diǎn)的都小于孩子節(jié)點(diǎn)，代碼原理和最大堆相似。

代碼如下：

void _AdjustUp(int child)
	{
		int parent = (child - 1) / 2;
		int size = _arr.size();
		while (child > 0)
		{
			if (_arr[child] > _arr[parent])
			{
				swap(_arr[child], _arr[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

下面我給出完整代碼，構(gòu)造函數(shù)用的是調(diào)整成大堆。為了讓代碼更簡潔，實(shí)現(xiàn)過程借用了庫函數(shù)中的vector。

代碼如下：

Heap.h中

#include<assert.h>
#include <vector>
template <class T>
class Heap
{
public:
	Heap()
		:_arr(NULL)
	{}
	//構(gòu)造函數(shù)
	Heap(const T*arr, size_t size)
	{
		_arr.reserve(size);
		for (size_t i = 0; i < size; i++)
		{
			_arr.push_back(arr[i]);
		}
		for (int j = (_arr.size() - 2) / 2; j >= 0; j--)
		{
			_AdjustDown(j, size);
		}
	}
	//拷貝構(gòu)造
	Heap(const vector<T>& h)
	{
		_arr.reserve(_arr.size());
		for (size_t i = 0; i < _arr.size(); i++)
		{
			_arr.push_back(h[i]);
		}
	}
	//先儲存在順序表中，在進(jìn)行下調(diào)
	void push(const T& x)
	{
		_arr.push_back(x);
		_AdjustUp(_arr.size()-1);
	}
	//刪除
	void pop()
	{
		size_t size = _arr.size();
		assert(size > 0);
		swap(_arr[0], _arr[size - 1]);//先把根結(jié)點(diǎn)和要?jiǎng)h除的結(jié)點(diǎn)交換
		_arr.pop_back();//然后刪除
		size = _arr.size();
		_AdjustDown(0, size);//最后上調(diào)
	}
	//堆是否為空
	bool Empty()
	{
		size_t size = _arr.size();
		assert(size >= 0);
		return size == 0;
	}
	//堆的大小
	size_t Size()
	{
		size_t size = _arr.size();
		assert(size >= 0);
		return size;
	}
	//訪問根結(jié)點(diǎn)
	T& Top()
	{
		size_t size = _arr.size();
		assert(size > 0);
		return _arr[0];
	}
	void Print()
	{
		for (int i = 0; i < Size(); i++)
		{
			cout << _arr[i] << " ";
		}
		cout << endl;
	}
protected:
	//下調(diào)
	void _AdjustDown(size_t parent, size_t size)
	{
		size_t child = 2 * parent + 1;
		while (child < size)
		{
			//child + 1 < size保證是最后一個(gè)節(jié)點(diǎn)
			if (child + 1 < size&&_arr[child] < _arr[child + 1])
			{
				child++;//孩子節(jié)點(diǎn)最大的一個(gè)節(jié)點(diǎn)
			}
			//交換
			if (_arr[child]>_arr[parent])
			{
				swap(_arr[child],_arr[parent]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}
	//上調(diào)
	void _AdjustUp(int child)
	{
		int parent = (child - 1) / 2;
		int size = _arr.size();
		while (child > 0)
		{
			if (_arr[child] > _arr[parent])
			{
				swap(_arr[child], _arr[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
protected:
	vector<T> _arr;
};

test.cpp中

#include<iostream>
using namespace std;
#include"Heap.h"
void Test()
{
	int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
	Heap<int> h(a, sizeof(a) / sizeof(a[0]));
	h.Print();

	h.push(20);
	h.Print();

	h.pop();
	h.Print();
	Heap<int> h2(h);
	h2.Print();
}
int main()
{
	Test();
	system("pause");
	return 0;
}

網(wǎng)頁題目：用模板實(shí)現(xiàn)堆
本文鏈接：http://bm7419.com/article0/pcdoio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、微信公眾號、搜索引擎優(yōu)化、服務(wù)器托管、網(wǎng)站內(nèi)鏈、網(wǎng)站營銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)