堆是什么

堆是一種特殊的完全二叉樹(shù)

如果你是初學(xué)者，你的表情一定是這樣的??

別想復(fù)雜

首先，你一定見(jiàn)過(guò)這種圖

咱們暫時(shí)不管數(shù)字

這就是一個(gè)堆

堆又分為最大堆和最小堆

最大堆

看這張圖

上面的節(jié)點(diǎn)的數(shù)都比下面的節(jié)點(diǎn)的數(shù)大，最上面的數(shù)是最大的，這就叫最大堆??

最小堆

還是一樣的數(shù)，看這張圖

這是一個(gè)最小堆，同最大堆，最上面的節(jié)點(diǎn)的數(shù)最小，上面的節(jié)點(diǎn)的數(shù)比下面的節(jié)點(diǎn)的數(shù)大

怎么樣，是不是很簡(jiǎn)單？

堆排序

堆排序的基本思想是利用堆，使在排序中比較的次數(shù)明顯減少使速度更快

堆排序的時(shí)間復(fù)雜度為O(n*log(n))， 非穩(wěn)定排序，原地排序(空間復(fù)雜度O(1))。

堆排序的關(guān)鍵在于建堆和調(diào)整堆，下面簡(jiǎn)單介紹一下建堆的過(guò)程：

可以用STL下的

make_heap()

具體步驟：

第1趟將索引0至n-1處的全部數(shù)據(jù)建大頂(或小頂)堆，就可以選出這組數(shù)據(jù)的最大值(或最小值)。將該堆的根節(jié)點(diǎn)與這組數(shù)據(jù)的最后一個(gè)節(jié)點(diǎn)交換，就使的這組數(shù)據(jù)中最大(最小)值排在了最后。

第2趟將索引0至n-2處的全部數(shù)據(jù)建大頂(或小頂)堆，就可以選出這組數(shù)據(jù)的最大值(或最小值)。將該堆的根節(jié)點(diǎn)與這組數(shù)據(jù)的倒數(shù)第二個(gè)節(jié)點(diǎn)交換，就使的這組數(shù)據(jù)中最大(最小)值排在了倒數(shù)第2位。

…

第k趟將索引0至n-k處的全部數(shù)據(jù)建最大(或最小)堆，就可以選出這組數(shù)據(jù)的最大值(或最小值)。將該堆的根節(jié)點(diǎn)與這組數(shù)據(jù)的倒數(shù)第k個(gè)節(jié)點(diǎn)交換，就使的這組數(shù)據(jù)中最大(最小)值排在了倒數(shù)第k位。

其實(shí)整個(gè)堆排序過(guò)程中, 我們只需重復(fù)做兩件事：

建堆(初始化+調(diào)整堆, 時(shí)間復(fù)雜度為O(n));

拿堆的根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)交換(siftdown, 時(shí)間復(fù)雜度為O(n*log n) ).

因而堆排序整體的時(shí)間復(fù)雜度為O(n*log n)

沒(méi)看懂可以看看這個(gè)圖

最終代碼

#include <iostream>
#include <stdlib.h>
using namespace std;
 
/*******************************************/
/*  堆排序
/******************************************/
 
void swap(int &a, int &b)  //位置互換函數(shù)
{
	int temp = a;
	a = b;
	b = temp;
}
 
 
void Heap(int array[], int length, int index)  //堆排序算法(大頂堆)
{
	int left = 2 * index + 1;  //左節(jié)點(diǎn)數(shù)組下標(biāo)
	int right = 2 * index + 2;  //右節(jié)點(diǎn)數(shù)組下標(biāo)
	int max = index;  //index是父節(jié)點(diǎn)
 
	if (left < length && array[left] > array[max])  //左節(jié)點(diǎn)與父節(jié)點(diǎn)比較
	{
		max = left;
	}
	
	if (right < length && array[right] > array[max])  //右節(jié)點(diǎn)與父節(jié)點(diǎn)比較
	{
		max = right;
	}
 
	if (array[index] != array[max])
	{
		swap(array[index], array[max]);
		Heap(array, length, max);  //遞歸調(diào)用
	}
}
 
 
void HeapSort(int array[], int size)  //堆排序函數(shù)
{
	for (int i = size / 2 - 1; i >= 0; i--)  // 創(chuàng)建一個(gè)堆
	{
		Heap(array, size, i);
	}
 
	for (int i = size - 1; i >= 1; i--)
	{
		swap(array[0], array[i]);  //將array[0]的最大值放到array[i]的位置上，最大值往后靠
		Heap(array, i, 0);  //調(diào)用堆排序算法進(jìn)行比較
	}
}
 
 
int main(void)  //主程序
{
	const int n = 6;  //數(shù)組元素的數(shù)量
	int array[n];
	cout << "請(qǐng)輸入6個(gè)整數(shù)：" << endl;
	for (int i = 0; i < n; i++)
	{
		cin >> array[i];
	}
 
	cout << endl;  //換行
 
	HeapSort(array, n);  // 調(diào)用HeapSort函數(shù)  進(jìn)行比較
 
	cout << "由小到大的順序排列后：" << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "Array" << "[" << i << "]" << " = " << array[i] << endl;
	}
 
	cout << endl << endl;  //換行
 
	system("pause");  //調(diào)試時(shí)，黑窗口不會(huì)閃退，一直保持
	return 0;
}

關(guān)于堆

C++中堆的應(yīng)用：make_heap, pop_heap, push_heap, sort_heap

函數(shù)說(shuō)明： make_heap將[start, end)范圍進(jìn)行堆排序，默認(rèn)使用less, 即最大元素放在第一個(gè)。

pop_heap將front（即第一個(gè)最大元素）移動(dòng)到end的前部，同時(shí)將剩下的元素重新構(gòu)造成(堆排序)一個(gè)新的heap。

push_heap對(duì)剛插入的（尾部）元素做堆排序。

sort_heap將一個(gè)堆做排序,最終成為一個(gè)有序的系列，可以看到sort_heap時(shí)，必須先是一個(gè)堆（兩個(gè)特性：1、最大元素在第一個(gè) 2、添加或者刪除元素以對(duì)數(shù)時(shí)間），因此必須先做一次make_heap.

到此這篇關(guān)于c++深入淺出講解堆排序和堆的文章就介紹到這了,更多相關(guān)c++ 堆排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論