首页 > 资讯 > 其他综合 > 正文

堆的构建、堆的插入、堆的删除、堆排序

17-02-09 来源：[db:作者]

收藏我要投稿

堆的构建、堆的插入、堆的删除、堆排序：n个元素的序列{k₁，k₂，…,k_n}当且仅当满足下列关系之一时，称之为堆。

情形1：k_i<= k_2i且k_i<= k_2i+1（最小化堆或小顶堆）

情形2：k_i>= k_2i且k_i>= k_2i+1（最大化堆或大顶堆）

其中i=1,2,…,n/2向下取整;

　　若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。

　　由此，若序列{k₁，k₂，…,k_n}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k₁,k₂,…,k_n}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

一般用数组来表示堆，i结点的父结点下标就为(i–1)/2。它的左右子结点下标分别为2*i+1和2*i+2。如第0个结点的左右子结点下标分别为1和2。

2.堆的插入

每次插入都是将先将新数据放在数组最后，由于从这个新数据的父结点到根结点必然为一个有序的序列，现在的任务是将这个新数据插入到这个有序序列中——这就类似于直接插入排序中将一个数据并入到有序区间中。

3.堆的删除

堆中每次都只能删除堆顶元素。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于根结点数据的“下沉”过程。

4.堆的建立

从无序序列建堆的过程就是一个反复调整的过程。若将此序列看成是一个完全二叉树，则最后一个非终端结点是第(n-2)/2个结点，由此调整过程只需从该结点开始，直到堆顶元素。

5.堆排序

若在输出堆顶的最小值之后，使得剩余n-1个元素的序列重建一个堆，则得到n个元素中的次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。

输出堆顶元素之后，以堆中最后一个元素替代之，此时根结点的左右子树均为堆，则仅需进行一次从上到下的调整即可重建一个堆。

如果你不理解请看其它2篇博客图解，一定会搞懂

6、代码实现如下

#include
#include
#define INIT_ARRAY_SIZE 50

int heap_size; //堆大小
int heap_cap_size;  //堆容量大小

/*函数声明*/  
//构建堆
void build_heap(int array[], int length);
//堆的调整
void max_heap_adjust(int array[], int index);
//堆的删除
void heap_delete(int array[], int value);
//堆的插入
void heap_insert(int** array, int value);
//堆排序
void heap_sort(int array[], int length);

/*返回以index为根的完全二叉树的左子树的索引，整个二叉树索引以0为开始*/  
int left(int index) {
	return ((index << 1) + 1);
}
/*返回以index为根的完全二叉树的右子树的索引，整个二叉树索引以0为开始*/ 
int right(int index) {
	return ((index << 1) + 2);
}
/*两个数的交换*/ 
void swap(int* a ,int* b) {
	int temp = *a;
		*a = *b;
		*b = temp;
	return;
}

void build_heap(int array[], int length) {
	heap_size = length;
	for (int i = ((heap_size - 1) >> 1); i >= 0; --i) {
		max_heap_adjust(array, i);
	}
}

void max_heap_adjust(int array[], int index) {
	int left_index = left(index);
	int right_index = right(index);
	int largest = index;
	//左子树和父节点进行对比
	if (left_index <= (heap_size-1) && array[left_index] > array[largest]) {
		largest = left_index;
	}
	//右子树和父节点进行对比
	if (right_index <= (heap_size-1) && array[right_index] > array[largest] ) {
		largest = right_index;
	}
	if (largest == index) {
		return;
	} else {
		//需要交换
		swap(&array[index], &array[largest]);
		//递归调用
		max_heap_adjust(array, largest);
	}
}

void heap_delete(int array[], int value) {
	int index = 0;
	for (index = 0; index < heap_size; index++) {
		if (array[index] == value) {
			break;
		}
	}
	array[index] = array[heap_size - 1];
	--heap_size;
	max_heap_adjust(array, index);
}

void heap_insert(int** array, int value) {
	int index = 0;
	int parent_index = 0;
	if (heap_size+1 > heap_cap_size) {
		*array = (int*) realloc(*array, 2*INIT_ARRAY_SIZE*sizeof(int));
	}
	(*array)[heap_size] = value; //一定要记得加上()既(*array)[heap_size] 如果写出*array[heap_size]肯定会出问题
	index = heap_size;
	heap_size++;//要记得这里堆大小变大了
	//和父节点对比，哪个大就往上移动
	while (index) {
		parent_index = ((index-1) >> 1);
		if ((*array)[parent_index] < (*array)[index]) {
			swap(&((*array)[parent_index]), &((*array)[index]));	
		}
		index = parent_index;
	}
}

void heap_sort(int array[], int length) {
	int old_heap_size  = heap_size;
	int i;
	for (i = length-1; i >= 1; --i) {
		swap(&array[i], &array[0]);
		--heap_size;
		max_heap_adjust(array, 0);
	}
	//恢复堆的大小
	heap_size = old_heap_size;
}

void print_array(int* a , int length) {
	for (int i =0; i < length; i++) {
		printf("%d\t", a[i]);
	}
	printf("\n");
}
int main() {
	int i = 0;
	int a[] = {9, 3, 7, 6, 5, 1, 10, 2};
	int *array = NULL;
	array = (int *)malloc(INIT_ARRAY_SIZE*sizeof(int));
	int length = sizeof(a)/sizeof(int);
	printf("数组的长度是:%d\n", length);
	for (i = 0; i < length; ++i) {
		array[i] = a[i];
	}
	printf("原始数组为\n");
	print_array(array, length);
	printf("堆的建立后的数组\n");
	build_heap(array, length);
	print_array(array, length);
	printf("堆排序后的数组为\n");
	heap_sort(array, length);
	print_array(array, length);
    //这个地方一定要记得先构建堆，不然下面执行删除和插入有问题
	build_heap(array, length);

	printf("删除数据10后的数组\n");
	heap_delete(array, 10);
	length--;
	print_array(array, length);

	printf("插入数据10后的数组\n");
	length++;
	heap_insert(&array, 10);
	print_array(array, length);

	printf("堆排序后的数组为\n");
	heap_sort(array, length);
	print_array(array, length);
	return 0;
}

运行结果：

点击复制链接与好友分享!回本站首页