欢迎来到军工软件开发人才培养基地——学到牛牛

数据结构之堆

时间:2024-05-06 07:01:10 来源:学到牛牛

堆的基本概念与结构:

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;

}