数据结构之堆
堆的基本概念与结构：
1、堆的概念：
堆是一种完全二叉树结构，分为最大堆和最小堆。根节点权值最大时被称为为最大堆或大根堆，根节点最小时则被称为最小堆或小根堆。
2、堆的性质：
首先，大根堆中的节点必定不会大于其父节点，小根堆中的节点必定不会小于其父节点。其次，堆一般是一颗完全二叉树。
· 完全二叉树一般采用数组存储。
· 完全二叉树是在满二叉树的基础上，最后一层的叶子节点在左边。
· 二叉树的每一层节点都达到最大值即为满二叉树。
3、堆的结构：
假设有数组：int arr[] = {1,7,9,11,23,45,69}; 此时，大根堆如下：
假设有数组：int arr[] = {69,45,23,11,9,7,1}; 此时，小根堆如下：
4、堆的操作：
堆的基本操作有：向上调整、向下调整、插入、删除、排序、遍历、判空、排序、获取堆顶... ...
向下调整：
此处以小堆为例，步骤如下：
· 设定根节点为当前节点A，比较左右子树的值，找出更小值，并将其标记为B。
· 比较A与B的值，若B < A，则不满足小根堆的规则，此时交换两者；反之则不需要交换。
· 将B设为新的根节点，重复上述步骤。
向上调整：
向上算法一般在创建堆时使用。假设有一个数组，此数组逻辑上是一颗完全二叉树，但不是堆。需要用算法将其构建为堆，此时从最后一个非叶子节点的子树开始调整，直到根节点为止。
以小根堆为例，步骤如下：
· 设定最后一个叶子节点为当前节点A，找到其父节点B。
· 比较A与B的值，若A < B，则不满足小根堆的规则，此时交换两者；反之则不需要交换。
· 将B设为新的当前节点，重复上述步骤。
插入：
将数据插入数组的最后，然后进行向上调整即可。
删除：
堆的删除一般指删除堆顶的数据，将堆顶数据与最后一个数据交换，然后删除最后一个数据，再进行向下调整即可。
排序：
· 将待排序的序列构造为一个大根堆，此时最大值为根节点。
· 将根节点与最后一个节点交换，此时最后一个节点为最大值。
· 再将剩余的节点构造为大根堆，重复上述步骤即可。
5、堆的代码实例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
struct heap
{
int size;
int max;
int *data;
};
// 初始化堆
void initHeap( struct heap *hp )
{
assert( hp != NULL );
hp->max = 0;
hp->size = 0;
hp->data = NULL;
}
void swap( int *numA, int *numB )
{
int temp = *numA;
*numA = *numB;
*numB = temp;
}
// 向下调整
void shiftDown( int *arr, int size, int cur )
{
int child = 2*cur + 1;
while( child < size )
{
if( (arr[child]>arr[child+1]) && (child+1<size) )
{
child++;
}
if( arr[child] < arr[cur] )
{
swap( arr+cur, arr+child );
cur = child;
child = cur*2 + 1;
}
else
{
break;
}
}
}
// 向上调整
void shiftUp( int *arr, int size, int cur )
{
int parent = (cur-1) / 2;
while( cur > 0 )
{
if( arr[cur] < arr[parent] )
{
swap(arr+cur, arr+parent);
cur = parent;
parent = (cur-1) / 2;
}
else
{
break;
}
}
}
// 创建堆
void creatHeap( struct heap *hp, int *arr, int n )
{
assert( hp != NULL );
hp->data = malloc(sizeof(int)*n);
memcpy(hp->data,arr,n*sizeof(int));
hp->max = n;
hp->size = n;
int i = 0;
for( i=(n-2)/2; i>=0; i-- )
{
shiftDown(hp->data, hp->size, i);
}
}
// 插入堆
void heapPush( struct heap *hp, int val )
{
assert( hp != NULL );
if( hp->size == hp->max )
{
int newSize = hp->max*2;
hp->data = realloc( hp->data, newSize );
hp->max = newSize;
}
hp->data[hp->size++] = val;
shiftDown( hp->data, hp->size, hp->size-1 );
}
// 堆排序
void sortHeap( struct heap *hp )
{
int i = 0;
for( i=(hp->size-2)/2; i>=0; i-- )
{
shiftDown( hp->data, hp->size, i );
}
int end = hp->size-1;
while( end > 0 )
{
swap( hp->data+0, hp->data+end );
shiftDown( hp->data, end, 0 );
end--;
}
}
// 堆删除
void heapPop( struct heap *hp )
{
if( hp->size > 0 )
{
swap( hp->data+0, hp->data+hp->size-1 );
hp->size--;
shiftDown( hp->data, hp->size, 0 );
}
}
// 获取堆顶
int heapTop( struct heap *hp )
{
assert( hp != NULL );
return hp->data[0];
}
/*
// 判空
bool heapEmpty( struct heap *hp )
{
if( (hp==NULL) || (hp->size==0) )
{
return true;
}
return false;
}*/
// 堆遍历
void showHeap( struct heap *hp )
{
assert( hp != NULL );
int i = 0;
for( i=0; i<hp->size; i++ )
{
printf("heap = %d \n",hp->data[i]);
}
}
int main()
{
struct heap hp;
initHeap( &hp );
int arr[] = {1,3,6,2,3,6,7,8,2};
creatHeap( &hp, arr, sizeof(arr)/sizeof(arr[0]) );
showHeap( &hp );
printf("head top is %d \n", heapTop(&hp));
return 0;
}
