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),调整第一个元素
**/