数据结构-堆 C与C++的实现

时间：2021-11-05 12:20:46

堆，是一种完全二叉树。而且在这颗树中，父节点必然大于（对于小顶堆为小于）子节点。

关于树的概念不了解可以看这里：http://www.cnblogs.com/HongYi-Liang/p/7231440.html

由于堆是一种完全二叉树，很适合保存为数组的形式。如下图示意的堆，红色数字为数组索引，黑色数字为数组的值，那么这个堆保存为数组的形式:heap={9,8,5,6,7,1,4,0,3,2};

值得注意的是，在堆中，若设父亲的索引为i，左儿子的索引刚好等于2i，而右儿子的索引等于2i+1。这个公式会大量地出现在下边的程序中。

关键概念：

大顶堆：树根元素为最大值往叶子递减，（父节点总是大于子节点）

小顶堆：树根元素为最小值往叶子递增，（父节点总是小于子节点）

 

下为一个大顶堆的示意图，父节点总是大于子节点

 数据结构-堆 C与C++的实现

 

在下面的程序中，C将以大顶堆的形式编写，C++以小顶堆的形式编写。

 

C语言

程序源码：

本例子为大顶堆，包含4个文件（如下图）

数据结构-堆 C与C++的实现

MaxHeap.c

数据结构-堆 C与C++的实现数据结构-堆 C与C++的实现
#include "MaxHeap.h"

bool MaxHeapConstructByBuffer(MaxHeap *heap,MAXHEAP_ELEM buff[],int length);
bool MaxHeapDesturct(MaxHeap *heap);
bool MaxHeap_getSize(MaxHeap *heap);
bool MaxHeap_isFull(MaxHeap *heap);
bool MaxHeap_isEmpty(MaxHeap *heap);
void MaxHeap_swap(MAXHEAP_ELEM *a,MAXHEAP_ELEM *b);
void MaxHeap_floating(MaxHeap *heap,int index);
void MaxHeap_sink(MaxHeap *heap, int index);
bool MaxHeap_push(MaxHeap *heap,MAXHEAP_ELEM data);
bool MaxHeap_push(MaxHeap *heap,MAXHEAP_ELEM data);
bool MaxHeap_pop(MaxHeap *heap,int index);
void MaxHeap_printfAll(MaxHeap *heap);

bool MaxHeapConstructByBuffer(MaxHeap *heap,MAXHEAP_ELEM buff[],int length)
{
int i;
if(NULL != heap->iDatas)
    {
return false;
    }
    heap->iHeapCapacity=length;
    heap->iHeapSize=0;
    heap->iDatas = (MAXHEAP_ELEM*)malloc(sizeof(MAXHEAP_ELEM)*length);
for(i=0;i<length;i++)
    {
        MaxHeap_push(heap,buff[i]);
    }
return true;
}

bool MaxHeapDesturct(MaxHeap *heap)
{
if(NULL == heap->iDatas)
    {
return false;
    }
free(heap->iDatas);
return true;
}

bool MaxHeap_getSize(MaxHeap *heap)
{
return heap->iHeapSize;
}

bool MaxHeap_isFull(MaxHeap *heap)
{
if(heap->iHeapCapacity == heap->iHeapSize)
    {
return true;
    }
return false;
}

bool MaxHeap_isEmpty(MaxHeap *heap)
{
if(0 == heap->iHeapSize)
    {
return true;
    }
return false;
}

void MaxHeap_swap(MAXHEAP_ELEM *a,MAXHEAP_ELEM *b)
{
    MAXHEAP_ELEM temp;
    temp=*a;
*a=*b;
*b=temp;
}

void MaxHeap_floating(MaxHeap *heap,int index)
{
int i;
for(i=index;i>0;i=(int)(i*0.5))
    {
if(heap->iDatas[i-1] > heap->iDatas[(int)(i*0.5-1)] )
        {
            MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[(int)(i*0.5-1)]);
        }
else 
        {
break;
        }
    }    
}


void MaxHeap_sink(MaxHeap *heap, int index)
{
int i=index;

while(i*2<=heap->iHeapSize)
    {
if(heap->iDatas[i-1] < heap->iDatas[i*2-1])//it compare to left child
        {
            MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[i*2-1]);
if(i*2+1<=heap->iHeapSize && heap->iDatas[i-1] < heap->iDatas[i*2])//it compare to right child
            {
                MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[i*2]);            
            }
/*index*/
            i=i*2;
        }
else if(i*2+1<=heap->iHeapSize && heap->iDatas[i-1] < heap->iDatas[i*2])//it compare to right child
        {
            MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[i*2]);
            i=i*2+1;
        }
else
        {
break;
        }
    }    
}

bool MaxHeap_push(MaxHeap *heap,MAXHEAP_ELEM data)
{
if( MaxHeap_isFull(heap))
return false;
    heap->iDatas[heap->iHeapSize]=data;
    heap->iHeapSize++;
    MaxHeap_floating(heap,heap->iHeapSize);

return true;
}

bool MaxHeap_pop(MaxHeap *heap,int index)
{
if(MaxHeap_isEmpty(heap))
return false;
    heap->iDatas[index]=heap->iDatas[heap->iHeapSize-1];
    heap->iHeapSize--;
    MaxHeap_sink(heap,index+1);

return true;
}

void MaxHeap_printfAll(MaxHeap *heap)
{
int i;
    printf("heap:");
for( i=0;i<heap->iHeapSize;i++)
    {
        printf("%d ",heap->iDatas[i]);
    }
    printf("\r\n");
}
View Code

MaxHeap.h

数据结构-堆 C与C++的实现数据结构-堆 C与C++的实现
#ifndef __MAXHEAP_H
#define __MAXHEAP_H

#include <stdlib.h>
#include <stdio.h>
#include "Mystdbool.h"

typedef int MAXHEAP_ELEM;
typedef struct 
{
int iHeapCapacity;
int iHeapSize;
    MAXHEAP_ELEM *iDatas;
}MaxHeap;

bool MaxHeapConstructByBuffer(MaxHeap *heap,MAXHEAP_ELEM buff[],int length);
bool MaxHeapDesturct(MaxHeap *heap);
bool MaxHeap_getSize(MaxHeap *heap);
bool MaxHeap_isFull(MaxHeap *heap);
bool MaxHeap_isEmpty(MaxHeap *heap);
void MaxHeap_swap(MAXHEAP_ELEM *a,MAXHEAP_ELEM *b);
void MaxHeap_floating(MaxHeap *heap,int index);
void MaxHeap_sink(MaxHeap *heap, int index);
bool MaxHeap_push(MaxHeap *heap,MAXHEAP_ELEM data);
bool MaxHeap_push(MaxHeap *heap,MAXHEAP_ELEM data);
bool MaxHeap_pop(MaxHeap *heap,int index);
void MaxHeap_printfAll(MaxHeap *heap);

#endif
View Code

Mystdbool.h(仅用于声明布尔类)

数据结构-堆 C与C++的实现数据结构-堆 C与C++的实现
#ifndef _MYSTDBOOL_H
#define _MYSTDBOOL_H

typedef enum Bool
{
false=0,
true,
}bool;




#endif
View Code

main.c

数据结构-堆 C与C++的实现数据结构-堆 C与C++的实现
#include "MaxHeap.h"



int main()
{
/*int buffer[10]={9,8,7,6,5,4,3,2,1,0};*/
int buffer[10]={0,1,2,3,4,5,6,7,8,9};
    MaxHeap heap={0};
    MaxHeapConstructByBuffer(&heap,buffer,10);
    MaxHeap_printfAll(&heap);
    MaxHeap_pop(&heap,0);
    MaxHeap_printfAll(&heap);
    MaxHeap_pop(&heap,0);
    MaxHeap_printfAll(&heap);
    system("pause");
return 0;
}
View Code

运行结果：

数据结构-堆 C与C++的实现

源码详解：

上浮：floating(int index) 

数据结构-堆 C与C++的实现

 

  1. 将堆第index个元素与它的父亲比较，若小于它的父亲，则与它父亲交换数值。
  2. 上述过程如果发生，则把它继续上浮。
void MaxHeap_floating(MaxHeap *heap,int index)
{
int i;
for(i=index;i>0;i=(int)(i*0.5))
    {
if(heap->iDatas[i-1] > heap->iDatas[(int)(i*0.5-1)] )
        {
            MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[(int)(i*0.5-1)]);
        }
else 
        {
break;
        }
    }    
}

 

添加元素：push(T data)

  1. 把元素添加到堆的最后。
  2. 并使用上浮方法把堆的最后一个元素上浮。
bool MaxHeap_push(MaxHeap *heap,MAXHEAP_ELEM data)
{
if( MaxHeap_isFull(heap))
return false;
    heap->iDatas[heap->iHeapSize]=data;
    heap->iHeapSize++;
    MaxHeap_floating(heap,heap->iHeapSize);

return true;
}

 

构建堆：MaxHeapConstructByBuffer()

数据结构-堆 C与C++的实现

  1. 用malloc为数据申请空间。
  2. 一个一个地将buff中的数据push()到堆中。
bool MaxHeapConstructByBuffer(MaxHeap *heap,MAXHEAP_ELEM buff[],int length)
{
    int i;
 if(NULL != heap->iDatas)
 {
 return false;
 }
 heap->iHeapCapacity=length;
 heap->iHeapSize=0;
 heap->iDatas = (MAXHEAP_ELEM*)malloc(sizeof(MAXHEAP_ELEM)*length);
 for(i=0;i<length;i++)
 {
 MaxHeap_push(heap,buff[i]);
 }
 return true;
}

下沉：

  1. 从根开始，用父节点与左子节点比较。若父节点大于左子，则交换它们的值
  2. 用父节点与右子节点比较。若父节点大于右子，则交换它们的值。
  3. 若上述情况发生了，则继续下沉，直到无法下沉为止。
void MaxHeap_sink(MaxHeap *heap, int index)
{
int i=index;

while(i*2<=heap->iHeapSize)
    {
if(heap->iDatas[i-1] < heap->iDatas[i*2-1])//it compare to left child
        {
            MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[i*2-1]);
if(i*2+1<=heap->iHeapSize && heap->iDatas[i-1] < heap->iDatas[i*2])//it compare to right child
            {
                MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[i*2]);            
            }
/*index*/
            i=i*2;
        }
else if(i*2+1<=heap->iHeapSize && heap->iDatas[i-1] < heap->iDatas[i*2])//it compare to right child
        {
            MaxHeap_swap(&heap->iDatas[i-1],&heap->iDatas[i*2]);
            i=i*2+1;
        }
else
        {
break;
        }
    }    
}

删除元素：pop(int index)

  1. 把堆的第index个元素删除，并把堆的最后一个元素放到index处。
  2. 把堆的第index个元素下沉
bool MaxHeap_pop(MaxHeap *heap,int index)
{
if(MaxHeap_isEmpty(heap))
return false;
    heap->iDatas[index]=heap->iDatas[heap->iHeapSize-1];
    heap->iHeapSize--;
    MaxHeap_sink(heap,index+1);

return true;
}

 

 

C++

程序源码：

本例子为小顶堆，包含2个文件（如下图）

数据结构-堆 C与C++的实现

MyMinHeap.h:

此文件中为小顶堆的类模板。

数据结构-堆 C与C++的实现数据结构-堆 C与C++的实现
#ifndef __MYMINHEAP_H
#define __MYMINHEAP_H
#include <iostream>
#include <vector>


using namespace std;


template <typename T>
class MyMinHeap
{
public:
    MyMinHeap(T buff[],int length);
    MyMinHeap(int capacity);
virtual ~MyMinHeap();
int getSize();
bool isFull();
bool isEmpty();
void swap(vector<T> &vec,int i,int j);
void floating(int index);
void sink(int index);
bool push(T data);
bool pop(int index);
//transval
void printfAll();
private:
int m_iHeapCapacity;
int m_iHeapSize;
    vector<T> m_vecData;
};


template <typename T>
MyMinHeap<T>::MyMinHeap(T buff[],int length)
{
    m_iHeapCapacity=length;
    m_iHeapSize=0;
    m_vecData.resize(length);
for(int i=0;i<length;i++)
    {
        push(buff[i]);
    }
}

template <typename T>
MyMinHeap<T>::    MyMinHeap(int capacity)
{
    m_iHeapCapacity=capacity;
    m_iHeapSize=0;
    m_vecData.resize(capacity);
}

template <typename T>
MyMinHeap<T>::~MyMinHeap()
{

}

template <typename T>
int MyMinHeap<T>::getSize()
{
return m_iHeapSize;
}

template <typename T>
bool MyMinHeap<T>::isFull()
{
if(m_iHeapSize>=m_iHeapCapacity)
    {
return true;
    }
return false;
}
template <typename T>
bool MyMinHeap<T>::isEmpty()
{
if(m_iHeapSize==0)
return true;
return false;
}

template <typename T>
void MyMinHeap<T>::swap(vector<T> &vec,int i,int j)
{
    T temp = vec[i];
    vec[i]=vec[j];
    vec[j]=temp;
}

template <typename T>
void MyMinHeap<T>::floating(int index)
{
    T temp;
for(int i=index;i>0;i*=0.5)
    {
if(m_vecData[i-1]<m_vecData[i*0.5-1] )
        {
            swap(m_vecData,i-1,i*0.5-1);
        }
else 
        {
break;
        }
    }    
}


template <typename T>
void MyMinHeap<T>::sink(int index)
{
int i=index;

while(i*2<=m_iHeapSize)
    {
if(m_vecData[i-1]>m_vecData[i*2-1])//it compare to left child
        {
            swap(m_vecData,i-1,i*2-1);
if(i*2+1<=m_iHeapSize && m_vecData[i-1]>m_vecData[i*2])//it compare to right child
            {
                swap(m_vecData,i-1,i*2);            
            }
/*index*/
            i=i*2;
        }
else if(i*2+1<=m_iHeapSize && m_vecData[i-1]>m_vecData[i*2])//it compare to right child
        {
            swap(m_vecData,i-1,i*2);
            i=i*2+1;
        }
else
        {
break;
        }
    }
}

template <typename T>
bool MyMinHeap<T>::push(T data)
{
if(isFull())
return false;
    m_vecData[m_iHeapSize]=data;
    m_iHeapSize++;
    floating(m_iHeapSize);

return true;
}

template <typename T>
bool MyMinHeap<T>::pop(int index)
{
if(isEmpty())
return false;
    m_vecData[index]=m_vecData[m_iHeapSize-1];
    m_iHeapSize--;
    sink(index+1);

return true;
}

template <typename T>
void MyMinHeap<T>::printfAll()
{
    cout<<"heap:";
for(int i=0;i<m_iHeapSize;i++)
    {
        cout<<m_vecData[i]<<" ";
    }
    cout<<endl<<endl;
}


#endif
View Code

 

main.h:

主程序用于测试运行。

数据结构-堆 C与C++的实现数据结构-堆 C与C++的实现
#include <iostream>
#include "MyMinHeap.h"
using namespace std;


int main()
{
int buffer[10]={9,8,7,6,5,4,3,2,1,0};
    MyMinHeap<int> heap(buffer,10);
    heap.printfAll();
    heap.pop(1);
    heap.printfAll();
    heap.push(1);
    heap.printfAll();
    system("pause");
return 0;
}
View Code

 

运行结果：

数据结构-堆 C与C++的实现

 

 

源码详解：

上浮：floating(int index)

  1. 将堆第index个元素与它的父亲比较，若小于它的父亲，则与它父亲交换数值。
  2. 上述过程如果发生，则把它继续上浮。
template <typename T>
void MyMinHeap<T>::floating(int index)
{
    T temp;
for(int i=index;i>0;i*=0.5)
    {
if(m_vecData[i-1]<m_vecData[i*0.5-1] )
        {
            swap(m_vecData,i-1,i*0.5-1);
        }
else 
        {
break;
        }
    }    
}

 

添加元素：push(T data)

  1. 把元素添加到堆的最后。
  2. 并使用上浮方法把堆的最后一个元素上浮。
template <typename T>
bool MyMinHeap<T>::push(T data)
{
if(isFull())
return false;
    m_vecData[m_iHeapSize]=data;
    m_iHeapSize++;
    floating(m_iHeapSize);

return true;
}

 

构造函数：使用数组构建堆：

连续使用push（）把buff中所有元素一个一个地加入堆中。

template <typename T>
MyMinHeap<T>::MyMinHeap(T buff[],int length)
{
    m_iHeapCapacity=length;
    m_iHeapSize=0;
    m_vecData.resize(length);
for(int i=0;i<length;i++)
    {
        push(buff[i]);
    }
}

 

下沉：

  1. 从根开始，用父节点与左子节点比较。若父节点大于左子，则交换它们的值
  2. 用父节点与右子节点比较。若父节点大于右子，则交换它们的值。
  3. 若上述情况发生了，则继续下沉，直到无法下沉为止。
template <typename T>
void MyMinHeap<T>::sink(int index)
{
int i=index;

while(i*2<=m_iHeapSize)
    {
if(m_vecData[i-1]>m_vecData[i*2-1])//it compare to left child
        {
            swap(m_vecData,i-1,i*2-1);
if(i*2+1<=m_iHeapSize && m_vecData[i-1]>m_vecData[i*2])//it compare to right child
            {
                swap(m_vecData,i-1,i*2);            
            }
/*index*/
            i=i*2;
        }
else if(i*2+1<=m_iHeapSize && m_vecData[i-1]>m_vecData[i*2])//it compare to right child
        {
            swap(m_vecData,i-1,i*2);
            i=i*2+1;
        }
else
        {
break;
        }
    }
}

 

删除元素：pop(int index)

  1. 把堆的第index个元素删除，并把堆的最后一个元素放到index处。
  2. 把堆的第index个元素下沉
template <typename T>
bool MyMinHeap<T>::pop(int index)
{
if(isEmpty())
return false;
    m_vecData[index]=m_vecData[m_iHeapSize-1];
    m_iHeapSize--;
    sink(index+1);

return true;
}

 

 

 

 

标签：

相关文章