# 算法导论复习:第六章 原

fzyz_sb

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

### fzyz_sb

modernizr
2014/05/22
28.1K
13

himayan46
2016/09/28
0
0

5.2 二叉树 我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正...

fzyz_sb
2013/12/07
0
2
ZOJ 3499. Median

地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4322 　　　　题意：寻找中位数。对于一个（浮点数）数组，如果含有奇数个元素，“中位数”就是排序后位于数组中...

hoodlum1980
2012/06/13
0
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础，在BAT的初面中，会涉及到比较多的java基础知识，所以比较重要，下面我介绍的书籍内容是由浅到深。 1.Thinking in java：这本书被称为Java的三大圣经之一，虽然书比...

android自学
07/25
0
0

CentOS7防火墙firewalld操作

firewalld Linux上新用的防火墙软件，跟iptables差不多的工具。 firewall-cmd 是 firewalld 的字符界面管理工具，firewalld是CentOS7的一大特性，最大的好处有两个：支持动态更新，不用重启服...

dingdayu

1
0

DannyCoder

2
0

qiang123

3
0
Spring Cloud Gateway 之 Only one connection receive subscriber allowed

ThinkGem

27
0

1. 认识观察者模式 1. 定义：定义对象之间一种一对多的依赖关系，当一个对象状态发生变化时，依赖该对象的其他对象都会得到通知并进行相应的变化。 2. 组织结构： Subject：目标对象类，会被...

4
0