10-1.c

数据结构的经典实现算法

#include "stdio.h"
#define  MAX_SIZE 100    /*  堆最大个数－1 */
#define FALSE 0
#define TRUE  1
#define SWAP(x, y, t)  ((t) = (x) , (x) = (y), (y) = (t))
typedef struct  info{
		int key;
		/* 其他数据 */
} element;
void verify_max(element heap[],int i,element item)
{/* 跟踪最大结点i到根，插入元素到正确的位置*/
	int grandparent = i / 4;
	while (grandparent)
		if (item.key > heap[grandparent].key) {
			heap[i] = heap[grandparent];
			i = grandparent;
			grandparent /= 4;
		}
    else
		break;
	heap[i] = item;
}
void verify_min(element heap[],int i,element item)
{/* 跟踪最小结点i到根，插入元素到正确的位置*/
	int grandparent = i / 4;
	while (grandparent)
		if (item.key < heap[grandparent].key) {
			heap[i] = heap[grandparent];
			i = grandparent;
			grandparent /= 4;
		}
    else
		break;
	heap[i] = item;
}
int level(element heap[ ],int parent)
{	
	if(heap[parent].key>heap[parent/2].key)
		return TRUE;
	else
		return FALSE;
}
void insert(element heap[ ],int *n,element item)
{    /*最大最小堆的插入*/
	int parent;
	(*n) ++;
	if (*n == MAX_SIZE) {
		printf("堆已经满了\n");
		exit(1);
	}
	parent = (*n)/2;
	if (!parent)
	/* 如果堆空，插入元素到第一个位置 */
		heap[1] = item;
	else switch(level(heap,parent)) {
       case FALSE:        /*最小层*/
              if (item.key < heap[parent].key) {
                heap[*n] = heap[parent];
                verify_min(heap, parent, item);
              }
              else
                verify_max(heap, *n, item);
              break;
       case TRUE:     /*最大层*/
              if (item.key > heap[parent].key) {
                heap[*n] = heap[parent];
                verify_max(heap, parent, item);
              }
              else
                verify_min(heap, *n, item);
	}
}
void main()
{
	element heap[MAX_SIZE];
	element x1,x2;
	x1.key=20;
	x2.key=30;
	insert(heap,0,x1);
	insert(heap,1,x2);
}