龙空技术网

堆排序_基本思想

coder人生 145

前言:

现时各位老铁们对“堆排序算法描述”大体比较珍视,你们都需要学习一些“堆排序算法描述”的相关内容。那么小编也在网络上搜集了一些关于“堆排序算法描述””的相关文章,希望大家能喜欢,小伙伴们快快来了解一下吧!

二叉堆的定义:二叉堆是完全二叉树或者是近似完全二叉树

二叉堆满足两个特性:

a.父节点的键值总是大于等于或小于等于任何一个子节点的键值

b.每个节点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)

大顶堆:父节点的键值总是大于或等于任何一个子节点的键值

小顶堆:父节点的键值总是小于或等于任何一个子节点的键值

算法思想:堆排序 = 堆构造 + 交换堆末尾元素与根节点 + 删除未节点 + 构造堆 + 交换...一次循环,

由于根节点必定是堆中最大或最小的元素,所以删除出来的元素序列也必定是升序或降序的。

void minHeapFixdown(int arr, int i, int count){	int j, temp;	temp = arr[i];		j = 2 * i + 1;		while(j < count)	{		if (j + 1 < count && arr[j + 1] < arr[j])		{			j++; //找出较小的子节点		}				if(arr[j] >= temp)		{			break; //如果较小的子节点比父节点大 直接返回		}				arr[i] = arr[j]; //设置父节点为较小节点		i = j; //调整的子节点作为新一轮的父节点		j = 2 * i + 1; //调整的子节点的子节点	}		arr[i] = temp;}void heapSort(int array[], int count) {    for (int i = (count - 1) / 2; i >= 0; i--) 	  {        // 构造小顶堆        minHeapFixdown(array, i, count);	  }     for (int i = count - 1; i >= 1; i--) {         // 交换根结点与最末节点        int temp = array[i];        array[i] = array[0];        array[0] = temp;         // 剩余的n-1个元素再次建立小顶堆        minHeapFixdown(array, 0, i);     }}

标签: #堆排序算法描述