溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
在二叉樹中，我們用兩種方法表示二叉樹，一個是鏈表，一個是數組，但是數組比較適用于滿二叉樹或者完全二叉樹。
堆數據結構是一種數組對象，它可以被視為一棵完全二叉樹結構。
堆結構的二叉樹存儲有兩種方法：
最大堆：每個父節點的都大于孩子節點。
最小堆：每個父節點的都小于孩子節點。
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
template<class T>
class Heap
{
public:
Heap()//無參類型的構造函數
{}
Heap(T *a, size_t size)//有參類型的構造函數
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
//建堆，用 向下調整 算法
//對于一個完全二叉樹，其結點的父子關系與數組的下標的關系：
//左子下標= 父結點下標*2+1
//右子下標=父結點下標*2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒數第一個非葉子結點（最后一個元素一定是非葉子結點的子節點）
{
_AdjustDown(j);
}
/*
在第一次寫時定義了j為size_t類型，由于j不管怎么運算都是無符號類型所以
j>=0并沒有起到限制的作用，導致了死循環
*/
}
public:
void Push(const T &x)//在最后加入一個節點
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);//向上調整，傳入最后一個元素下標（調整x的位置）
}
void Pop()//把最大的刪掉（根）
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//把根節點和最后一個節點交換
_a.pop_back();//刪掉最后一個節點
_AdjustDown(0);//向下調整
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)//時間復雜度O(log2(N))
{
size_t child = parent * 2 + 1; //找到其左孩子
while (child < _a.size())
{
if ((child + 1) < _a.size() && _a[child] < _a[child + 1])//若左孩子小于右孩子（且必須結點下標不超過范圍）
{
++child;//指向大的
}
if (_a[child]>_a[parent])//若孩子大于父，則把大的放在父結點上
{
swap(_a[child], _a[parent]);
parent = child;//父和子調整后要繼續向下調整交換后的子節點
child = parent * 2 + 1;//現在這個調整后的節點的子節點
}
else
break;
}
}
void _AdjustUp(size_t child)//時間復雜度O(log2(N))
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_a[child] > _a[parent])
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
vector<T> _a;
};測試函數
void test()
{
int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int> h2(a, 10);
h2.Push(3);
h2.Push(4);
h2.Print();
h2.Push(100);
h2.Print();
h2.Pop();
h2.Print();
h2.Pop();
h2.Print();
}
int main()
{
test();
getchar();
return 0;
}上面實現了最大堆，最小堆方法同最大堆，但是再在類中重新一遍則會使程序的可維護性降低，所以我們用仿函數來實現。
仿函數
仿函數就是使一個類使用看上去像一個函數，其實現就是類中實現一個operator().這個類就有了類似函數的行為。
struct Free{ void operator()(void *ptr) { free( ptr); }};void Testsharedptr(){int *p1=(int*)malloc(sizeof(int)*10);shared_ptr<int>sp1(p1,Free());//在使用完后自動釋放p1}用仿函數實現最大堆與最小堆
template<class T>
struct Less
{
bool operator()(const T&left, const T&right)
{
return left < right;
}
};
template<class T>
struct Greater
{
bool operator()(const T&left, const T&right)
{
return left>right;
}
};
template<class T,class compare=Greater<T>>
class Heap
{
public:
Heap()//無參類型的構造函數
{}
Heap(T *a, size_t size)//有參類型的構造函數
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
//建堆，用 向下調整 算法
//對于一個完全二叉樹，其結點的父子關系與數組的下標的關系：
//左子下標= 父結點下標*2+1
//右子下標=父結點下標*2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒數第一個非葉子結點（最后一個元素一定是非葉子結點的子節點）
{
_AdjustDown(j);
}
}
public:
void Push(const T &x)//在最后加入一個節點
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);//向上調整，傳入最后一個元素下標（調整x的位置）
}
void Pop()//把最大的刪掉（根）
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//把根節點和最后一個節點交換
_a.pop_back();//刪掉最后一個節點
_AdjustDown(0);//向下調整
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)//時間復雜度O(log2(N))
{
size_t child = parent * 2 + 1; //找到其左孩子
compare com;
while (child < _a.size())
{
if ((child + 1) < _a.size() && com(_a[child+1],_a[child]))
{
++child;
}
if (com(_a[child],_a[parent]))//
{
swap(_a[child], _a[parent]);
parent = child;//父和子調整后要繼續向下調整交換后的子節點
child = parent * 2 + 1;//現在這個調整后的節點的子節點
}
else
break;
}
}
void _AdjustUp(size_t child)//時間復雜度O(log2(N))
{
size_t parent = (child - 1) / 2;
compare com;
while (child > 0)
{
if (com(_a[child] , _a[parent]))
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
vector<T> _a;
}; 這樣就實現了最大堆與最小堆，通過仿函數，程序的可維護性好于在類中寫一個最大堆寫法和最小堆寫法。
測試
void test1()
{
int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
int b[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int,Less<int>> h2(a, 10);//最小堆
h2.Push(3);
h2.Push(4);
h2.Print();
h2.Push(100);
h2.Print();
h2.Pop();
h2.Print();
h2.Pop();
h2.Print();
Heap<int>h3(b);//最大堆
h3.Push(3);
h3.Push(4);
h3.Print();
h3.Push(100);
h3.Print();
h3.Pop();
h3.Print();
h3.Pop();
h3.Print();
}堆的應用：
1.堆排序
分析：由于在大堆或者小堆排完后，只能保證每個小樹為大堆或者小堆，故還需要進行排序才能使數組元素完全依次排列。
所以我們先用大堆排列后，使堆頂元素為大元素，再依次將堆頂元素和未交換的最后一個元素交換，交換完成后再將除了大的元素之外的元素進行交換
/******************************
堆排序
盡建立一個大堆，每次把堆頂的元素和最后一個還未交換的元素交換
*/
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child < size)
{
if (a[child]<a[child + 1]&&child+1<size)
{
child++;
}
if (a[child] > a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int *a, int n)
{
assert(a);
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a,i,n);//大堆向下調整
}
for (int i = 0; i < n; i++)
{
swap(a[n - 1 - i],a[0]);
AdjustDown(a, 0, n - 1 - i);
}
}2.求N個元素中前K個最大的數
分析：建立一個小堆存放前K個元素，小堆的堆頂元素為前K個中最小的值，剩下N-K個數中依次和堆頂元素相比較，若大于堆頂元素，入堆，每入堆一個元素再小堆排序一次，使堆頂元素總為這K個元素的最小值；若小于堆頂元素，則繼續下一個數比較。當N-K個元素全比較完，堆中這K個元素就是最大的前K個數。
/*
從N個數中找到K個最大的數
建立一個小堆，大小為K,每次從第N-K的數據中取出一個和堆頂元素比較
*/
const int N = 1000000;
const int K = 100;
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child <size)
{
if (child+1<size&&a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void GetTopK(int *a)
{
assert(K < N);
int top[100];
for (size_t i = 0; i < 100; i++)
{
top[i] = a[i];
}
//建一個小堆，向下調整
for (int i = (K - 2) / 2; i>=0; i--)
{
AdjustDown(top, i, K);
}
//從剩下的N-K的數據中拿數據和堆頂元素比較，若小于堆頂元素，則入堆
for (size_t j = K; j < N ; j++)
{
if (a[j]<top[0])
{
top[0] = a[j];
AdjustDown(top, 0, K);
}
}
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
