fzyz_sb 发表于4年前

• 发表于 4年前
• 阅读 17
• 收藏 0
• 评论 0

1. 维护堆的性质

``````#include <stdio.h>

void swap( int *px, int *py )
{
int temp = *px;
*px = *py;
*py = temp;
}
void max_heapify( int *A, int i, int len )
{
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = 0;
if ( left <= len && A[ left ] > A[ i ] ){
largest = left;
}
else{
largest = i;
}
if ( right <= len && A[ right ] > A[ largest ] ){
largest = right;
}

if ( largest != i ){
swap( &A[ i ], &A[ largest ] );
max_heapify( A, largest, len );
}
}

int main( void )
{
int A[ 10 ] = { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
int i = 0;
max_heapify( A, 1, 9 );

for ( i = 0; i < 10; i++ ){
printf("%d ", A[ i ] );
}
printf("\n");

return 0;
}``````

2. 建堆

``````#include <stdio.h>

void swap( int *px, int *py )
{
int temp = *px;
*px = *py;
*py = temp;
}
void max_heapify( int *A, int i, int len )
{
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = 0;
if ( left < len && A[ left ] > A[ i ] ){
largest = left;
}
else{
largest = i;
}
if ( right < len && A[ right ] > A[ largest ] ){
largest = right;
}

if ( largest != i ){
swap( &A[ i ], &A[ largest ] );
max_heapify( A, largest, len );
}
}

void build_max_heap( int *A, int len )
{
int		index = len / 2 - 1;
for ( ; index >= 0; index-- ){
max_heapify( A, index, len );
}
}

int main( void )
{
int		i = 0;
int		A[ 10 ];
for ( i = 0; i < 10; i++ ){
A[ i ] = i;
}
build_max_heap( A, 10 );

for ( i = 0; i < 10; i++ ){
printf("%d ", A[ i ] );
}
printf("\n");

return 0;
}``````

3. 堆排序算法

``````#include <stdio.h>
#include <time.h>

#define SIZE 100

void swap( int *px, int *py )
{
int temp = *px;
*px = *py;
*py = temp;
}
void max_heapify( int *A, int i, int len )
{
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = 0;
if ( left < len && A[ left ] > A[ i ] ){
largest = left;
}
else{
largest = i;
}
if ( right < len && A[ right ] > A[ largest ] ){
largest = right;
}

if ( largest != i ){
swap( &A[ i ], &A[ largest ] );
max_heapify( A, largest, len );
}
}

void build_max_heap( int *A, int len )
{
int		index = len / 2 - 1;
for ( ; index >= 0; index-- ){
max_heapify( A, index, len );
}
}

void heapsort( int *A, int len )
{
int		i = 0;
build_max_heap( A, len );
for ( i = len - 1; i >= 1; i-- ){
swap( &A[ i ], &A[ 0 ] );
len -= 1;
max_heapify( A, 0, len );
}
}

int main( void )
{
int		A[ SIZE ];
int		i = 0;
srand( ( unsigned int )time( NULL ) );
for ( i = 0; i < 100; i++ ){
A[ i ] = rand() % 100;
}
heapsort( A, 100 );

for ( i = 0; i < 100; i++ ){
printf("%d ", A[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}
printf("\n");

return 0;
}``````

4. 优先队列

``````#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SIZE 10

void swap( int *px, int *py )
{
int temp = *px;
*px = *py;
*py = temp;
}
void max_heapify( int *A, int i, int len )
{
int left = i * 2 + 1;
int right = i * 2 + 2;
int largest = 0;
if ( left < len && A[ left ] > A[ i ] ){
largest = left;
}
else{
largest = i;
}
if ( right < len && A[ right ] > A[ largest ] ){
largest = right;
}

if ( largest != i ){
swap( &A[ i ], &A[ largest ] );
max_heapify( A, largest, len );
}
}

void build_max_heap( int *A, int len )
{
int		index = len / 2 - 1;
for ( ; index >= 0; index-- ){
max_heapify( A, index, len );
}
}

void heapsort( int *A, int len )
{
int		i = 0;
build_max_heap( A, len );
for ( i = len - 1; i >= 1; i-- ){
swap( &A[ i ], &A[ 0 ] );
len -= 1;
max_heapify( A, 0, len );
}
}

int heap_maximum( int *A ){
return A[ 0 ];
}

int heap_extract_max( int *A, int *len )
{
int max = INT_MIN;
if ( *len < 1 ){
printf("heap underflow");
return max;
}
max = A[ 0 ];
A[ 0 ] = A[ *len - 1 ];
*len -= 1;
max_heapify( A, 0, *len );

return max;
}

void heap_increase_key( int *A, int len, int key )
{
int		index = len;
A[ index ] = key;
while ( index >= 0 && A[ ( index - 1 ) / 2 ] < A[ index ] ){
swap( &A[ ( index - 1 ) / 2 ], &A[ index ]);
index = ( index - 1 ) / 2;
}
}

int main( void )
{
int		A[ SIZE ];
int		i = 0;
int		len = SIZE;
srand( ( unsigned int )time( NULL ) );
for ( i = 0; i < SIZE; i++ ){
A[ i ] = rand() % SIZE;
}

build_max_heap( A, len );

for ( i = 0; i < SIZE; i++ ){
printf("%d ", A[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}
printf("\n");

printf("max element is:%d\n", heap_maximum( A ) );
heap_extract_max( A, &len );
heap_increase_key( A, len, 6 );
for ( i = 0; i < SIZE; i++ ){
printf("%d ", A[ i ] );
if ( 0 == ( i + 1 ) % 10 ){
printf("\n");
}
}
printf("\n");

return 0;
}``````

×