堆数据结构的实现以及堆排序

堆数据结构的实现以及堆排序

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;
}

本文永久更新链接地址：