堆數據結構的實現以及堆排序

1、堆的數據結構使用數組進行存儲的

2、堆的數據結構按照完全二叉樹的結構進行描述，所以這裡關於堆的孩子節點和父節點的關系，構成了堆數據中數據獲取的一個入口，下標為i的父節點的兩個孩子節點的下標分別是2*i ,2*i+1 不同的起始下標，表示可能有所不同。

3、最大堆可以用於排序，復雜度在O(Nlog(N)),對還是實現優先權隊列的數據結構基礎

4、下面的代碼詳細描述了最大堆的一些關鍵操作

#ifndef MAXHEAP_H
#define MAXHEAP_H
#include <memory.h>
#include <iostream>
using namespace std;

/**
最大堆
*/

class MaxHeap
{
public:
int heapSize;
int * heap;
public:
MaxHeap();
MaxHeap(int heapSize);
virtual ~MaxHeap();

void output_heap();
void init_heap(int a[],int n);

int left(int i);
int right(int i);

void max_heapify(int i);
void max_heapify2(int i);

void build_max_heap();
void heap_sort();

};

#endif // MAXHEAP_H

#include "MaxHeap.h"

MaxHeap::MaxHeap(){
}

MaxHeap::~MaxHeap(){
delete []heap;
}

MaxHeap::MaxHeap(int heapSize):heapSize(heapSize){
heap = new int [heapSize] ;
memset(heap,0,sizeof(int)*heapSize);
}

//左孩子的index
int MaxHeap::left(int i){//下標從0開始的原因
return 2*i+1;
}

//右孩子的index
int MaxHeap::right(int i){
return 2*i +2;
}

/**
輸出堆的內容
**/
void MaxHeap::output_heap(){
for(int i=0;i<heapSize;++i){
cout<<heap[i]<<" ";
}
cout<<endl;
}

/**
利用數組初始化堆內容
**/
void MaxHeap::init_heap(int a[], int n){
if(n>heapSize)return ;
else{
heapSize=n;
//memcpy(heap,a,heapSize);
for(int i=0;i<heapSize;++i){
heap[i]=a[i];
}
}

}

/**
調整堆內數組使得其滿足堆的性質
調整從i節點開始，這個操作可以保證i節點及其子孫節點都滿足
最大堆的特點
*/

void MaxHeap::max_heapify(int i){

int l= left(i);
int r= right(i);
int max_index=0;
//最大孩子的下標
if(l<heapSize&&heap[l]>heap[i]){
max_index=l;
}else {
max_index=i;
}
if(r<heapSize&&heap[r]>heap[max_index]){
max_index=r;
}

if(max_index!=i){
swap(heap[i],heap[max_index]);
max_heapify(max_index);//防止造成子孫節點中出現不滿足堆的性質的情況發生
}
}

//堆調整的非遞歸代碼實現

void MaxHeap::max_heapify2(int i){
while(i<heapSize/2){
int l = left (i);
int r = right (i);
int max_index=0;
if(r<heapSize){
max_index = heap[l] > heap[r] ? l : r;
max_index = heap[max_index] > heap[i] ? max_index : i;
}else{
max_index = heap[l] > heap[i] ? l:i;
}
if(max_index!=i){
swap(heap[i],heap[max_index]);
i = max_index;
}
}
}

/**
堆的建立操作
*/

void MaxHeap::build_max_heap(){
for(int i= heapSize/2 +1;i>=0;--i){//從第一個非葉子節點開始調整為最大堆特征
max_heapify(i);
}
}

/**
堆排序，將最後一個元素同堆頂元素交換
每次都能保證取得的是當前最大的元素
max_heapfy(0),調整第一個元素
**/

void MaxHeap::heap_sort(){
build_max_heap();
int t = heapSize;
for(int i=heapSize-1;i>0;--i){
swap(heap[i],heap[0]);
heapSize--;
max_heapify(0);//取出之後對造成的不滿足最大堆進行調整
}
heapSize=t;
}