精华内容
下载资源
问答
  • 和堆排序

    千次阅读 2014-04-16 16:11:35
    堆是一种灵巧的、部分有序的数据结构,它尤其适合用来实现优先队列。 优先队列是元素的一个集合,其中每个元素都包含一个被称为元素优先级的可排序属性。优先队列支持下面的操作:...第二部分讲解堆排序。 【第一部分:

    是一种灵巧的、部分有序的数据结构,它尤其适合用来实现优先队列。

    优先队列是元素的一个集合,其中每个元素都包含一个被称为元素优先级的可排序属性。优先队列支持下面的操作:

    • 找出一个具有最高优先级的元素(即最大元素);
    • 删除一个具有最高优先级的元素;
    • 添加一个元素到集合中。

    通过采用堆这种数据结构可以高效实现这些操作。

    下文分两部分:第一部分介绍堆;第二部分讲解堆排序。

    【第一部分:堆的基本概念】

    堆的定义

    堆可以定义为一棵二叉树,树的节点中包含键(每个节点一个键),并且满足下面两个条件:

    1. 树的形状要求--这棵二叉树是基本完备的(或者简称完全二叉树),这意味着,树的每一层都是满的,除了最后一层最右边的元素有可能缺位。
    2. 父母优势要求--每一个节点的键都要大于或等于它子女的键(对于任何叶子我们认为这个条件都是自动满足的)。(最大堆)

    在堆中,键值是从上到下排序的。在任何从根到某个叶子的路径上,键值的序列式递减的。键值之间不存在从左到右的次序。在树的同一层的节点之间,不存在任何关系。在同一节点的左右子树之间也没有任何关系。

    堆的重要特征:

    1. 只存在一棵n个节点的完全二叉树。它的高度等于log2n。
    2. 堆的根总是包含了堆的最大元素。
    3. 堆的一个节点以及该节点的子孙也是一个堆。
    4. 可以用数组来实现堆,方法是用从上到下、从左到右的方式来记录堆的元素。为了方便起见,可以在这种数组从1到n的位置上存放堆元素,留下H[0](可以在其中放一个限位器)。在这种表示法中:
    a.  父母节点的键将会位于数组的前[n / 2]个位置中,而叶子节点的键将会占据后[n / 2]个位置。

    b.  在数组中,对于一个位于父母位置i(1<=i<=[n / 2])的键来说,它的子女将会位于2i和2i+1,相应地,对于一个位于i(2<=i<=n)的键来说,它的父母将会位于[i/2]。

    我们可以将堆定义为一个数组H[1…n],其中,数组前半部分中每个位置i上的元素,总是大于等于位置2i和2i+1中的元素。

    对于i=1,…,[n / 2], H[i]>=max{H[2i], H[2i+1]}

    自底向上堆构造算法

    从最后的父母节点开始,到根为止,检查这些节点的键是否满足父母优势要求。如果该节点不满足,则把节点的键K和它子女的最大键进行交换,然后再检查在新位置上,K是不是满足父母优势要求。这个过程一直持续到,对K的父母优势要求满足为止。对于以当前父母节点为根的子树,在完成了它“堆化”以后,该算法对于该几点的直接前趋进行同样的操作,直到对树的根完成了这种操作以后,该算法就停止。

    算法   HeapBottomUp(H[1..n])

        //用自底向上算法,从给定数组的元素中构建一个堆

        //输入:一个可排序元素的数组H[1..n]

        //输出:一个堆H[1..n]

    for    i <- [n / 2]   downto  1  do

    k <- i; v <- H[k]

    heap <- false

    while not  heap  and 2 * k <= n  do

    j <- 2 * k

    if  j < n 

    if  H[j] < H[j+1]     j <- j + 1

    if  v >= H[j]

    heap <- ture

    else  H[k] <- H[j];  k <- j

    H[k] <- v


    从堆中删除最大的键

    第一步:根的键和堆的最后一个键K做交换。

    第二步:堆的规模减一。

    第三步:严格按照自底向上堆构造算法把K沿着树向下删选,来对这棵较小的树进行“堆化”。验证K是否满足父母优势:如果它满足,操作完成;如果不满足,K和它较大的子女做交换;然后重复这个操作,直到K在新位置中满足了父母优势要求为止。

    【第二部分:堆排序】

    堆排序是由J.W.J.Williams提出。堆排序的时间效率输入O(nlogn)。这个算法分为两步:
    第一步:(构造堆)为一个给定的数组构造一个堆。
    第二部:(删除最大键)对剩下的堆应用n-1次根删除操作。
    对于堆的数组实现来说,一个正在被删除元素师位于最后的,所以结果数组将敲好是按照升序排列的原始数组。

    代码实现

    #include <stdio.h>
    #include <stdlib.h>
    
    //数组从1到n的位置上存放堆元素,a[0]不参与构造堆。
    //可以将a[0]空着,也可以在其中放一个限位器。
    
    /**********自底向上构造最大堆**************/
    void HeapBottomUp(int a[], int n)
    {
    	int i, j, k;
    	int tmp;
    	bool heap;
    	for(i = n / 2; i > 0; i--)
    	{
    		tmp = a[i];
    		k = i;	//父结点
    		heap = false;
    		while(!heap && 2 * k <= n)
    		{
    			j = 2 * k;
    			if(j < n)
    				if(a[j] < a[j + 1])
    					j = j + 1;
    			if(tmp >= a[j])
    				heap = true;
    			else
    			{
    				a[k] = a[j]; //较小父结点往下移
    				k = j;
    			}
    		}
    		a[k] = tmp;
    	}
    }
    
    /**********自底向上调整最大堆**************/
    void FixHeapBottomUp(int a[], int n)
    {
    	int i, j;
    	int tmp;
    	bool flag;
    	tmp = a[n];
    	i = n;
    	j = i / 2;
    	flag = true;
    	while(flag && j > 0)
    	{
    		if(a[j] >= tmp)
    			flag = false;
    		else
    		{
    			a[i] = a[j]; //较小父结点往下移
    			i = j;
    			j = i / 2;
    		}
    	}	
    	a[i] = tmp;
    }
    
    /**********自顶向下调整最大堆**************/
    void FixHeapUpBottom(int a[], int n)
    {
    	int tmp;
    	int i, j;
    	int flag;
    	tmp = a[1];
    	flag = true;
    	i = 1;
    	j = 2 * i;
    	while(flag && j <= n)
    	{
    		if(j + 1 <= n && a[j + 1] > a[j] )
    			j = j + 1;
    		if(a[j] <= tmp)
    			flag = false;
    		else
    		{
    			a[i] = a[j]; //较大子结点往上移
    			i = j;
    			j = 2 * i;
    		}
    	}
    	a[i] = tmp;
    }
    /**********插入一个数**************/
    void InsertNumber(int a[], int n, int num)
    {
    	int i, j;
    	a[n] = num;
    	FixHeapBottomUp(a, n);
    }
    
    /**********删除最大键**************/
    int DeleteNumber(int a[], int n)
    {
    	int tmp;
    	tmp = a[1];
    	a[1] = a[n];
    	a[n] = tmp;
    	FixHeapUpBottom(a, n - 1);
    	return tmp;
    }
    
    /**********堆排序**************/
    void HeapSort(int a[], int n)
    {
    	int i;
    	HeapBottomUp(a, n);
    	for(i = n; i > 1; i--)
    		DeleteNumber(a, i);
    }
    
    int main(int argc, const char *argv[])
    {
    	int a[7] = {0, 2, 9, 7, 6, 5, 8 };
    	int n = sizeof(a) / sizeof(int);
    	HeapSort(a, n - 1);
    	for(int i = 1; i < 7; i ++)
    		printf("%d ", a[i]);
    	return 0;
    }


    展开全文
  • 排序算法之堆和堆排序

    千次阅读 2013-11-03 00:03:01
    和堆排序思想,以及堆排序算法实现过程。

    一、什么是堆

    1. 堆实际上是一棵完全二叉树;
    2. 对于n个关键字序列 [ K0,K1,…,K(n-1) ],一般采用数组方式存储;
    3. 任何一非叶节点的关键字满足如下性质:
      • 若ki<=k(2i+1)且ki<=k(2i+2)(0≤i≤ n-1),称之为小根堆;
      • 若ki>=k(2i+1)且ki>=k(2i+2)(0≤i≤ n-1),称之为大根堆.

    二、堆排序

    堆排序思想 充分利用了堆顶关键字最大或最小的特性,从而可以快速选取一组数中的最大值或最小值。

    堆排序分为两个步骤构堆  调整堆。

    以大根堆为例,堆排序过程如下:
    1. 将初始待排序关键字序列(R0,R1....Rn-1)构建成大顶堆,此堆为初始的无序区;
    2. 将堆顶元素与堆尾元素交换,堆的长度减1, 此时得到新的无序区和新的有序区;
    3. 由于交换后新的堆顶可能违反堆的性质, 因此需要对当前无序区调整为新堆;
    4. 不断重复过程2和3直到有序区的元素个数为n-1,则整个排序过程完成

    三、算法实现

    堆的基本操作分为向上调整和向下调整,利用向上调整操作构建堆,堆顶元素和堆尾交换后,堆长度减1,利用向下调整操作从堆顶开始调整生成新堆。
    #include <iostream>
    using namespace std;
    
    inline void swap(int arr[], int a, int b) {
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    
    // 向上调整堆	:从堆尾开始向堆顶调整
    // 	arr	: 堆数组指针
    //	n	: 堆尾元素位置
    void shiftUp(int arr[], int n) {
    	if (n < 1) {
    		return;
    	}
    	int b = (n - 1) / 2;
    	int a = n;
    	while (a > 0) {
    		if (arr[a] > arr[b]) {
    			swap(arr, a, b);
    			a = b;
    			b = (b - 1) / 2;
    		} else {
    			break;
    		}
    	}
    }
    
    // 向下调整堆	:从堆顶开始向堆尾调整
    // 	arr	: 堆数组指针
    //	n	: 堆尾元素位置
    void shiftDown(int arr[], int n) {
    	if (n < 1) {
    		return;
    	}
    	int a, b = 0;
    	int maxLeaf = (n - 1) / 2;
    	while (b <= maxLeaf) {
    		a = 2 * b + 1;
    		if (a < n && arr[a] < arr[a + 1]) {
    			a++;
    		}
    		if (arr[b] < arr[a]) {
    			swap(arr, b, a);
    			b = a;
    		} else {
    			break;
    		}
    	}
    }
    
    // 堆排序算法
    //	arr	: 待排序的数组指针
    //	len	: 数组长度
    void heapSort(int* arr, int len) {
    	int index;
    	// 构建堆
    	for (index = 1; index < len; index++) {
    		shiftUp(arr, index);
    	}
    	// 调整堆
    	for (index = len - 1; index > 0;) {
    		swap(arr, 0, index);
    		index--;
    		shiftDown(arr, index);
    	}
    }
    
    // 测试算法
    int main() {
    	int arr[] = { 213, 43, 43, 123, 45, 52, 67, 234, 452, 5, 67 };
    	int len = 11;
    
    	cout << "Before sorting:" << endl;
    	for (int i = 0; i < len; i++) {
    		cout << arr[i] << "\t";
    	}
    	cout << endl << endl;
    
    	heapSort(arr, len);
    
    	cout << "After Sorting:" << endl;
    	for (int i = 0; i < len; i++) {
    		cout << arr[i] << "\t";
    	}
    	cout << endl;
    
    	return 0;
    }
    
    执行结果如下:



    四、算法分析

    堆排序时间复杂度最好和最坏的情况下都是: O(n*log2(n)),堆排序空间复杂度为: O(1)

    若关注排序最坏的情况,宜选择堆排序。


    展开全文
  • 和堆排序:为什么说堆排序没有快速排序快

    千次阅读 多人点赞 2019-01-22 10:23:50
    堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。 前面我们学过快速排序,平均情况下,它的时间复杂度为O(logn)。尽管这两种排序算法的时间复杂度...

    ------ 本文是学习算法的笔记,《数据结构与算法之美》,极客时间的课程 ------

    我们今天讲另外一种特殊的树,“堆(Heap)”。堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。

    前面我们学过快速排序,平均情况下,它的时间复杂度为O(logn)。尽管这两种排序算法的时间复杂度都是O(nlogn),甚至堆排序比快速排序的时间复杂度还要稳定,但是,是实际软件开发中,快速的排序的性能要比堆排序好,这是为什么呢?

    如何理解“堆”?

    前面我们提到,堆是一种特殊的树。我们现在来看看,什么样的树才是堆。

    • 堆是一个完全二叉树;
    • 堆中每个节点的值都必须大于等于(或小于等于)其子树中每个节点的值。
      在这里插入图片描述

    其中第1个和第2个是大顶堆,第3 个是小顶堆,第4个不是堆。除此之外,从图中还可以看出来,对于同一组数据,我们可以构建多种不再形态的堆。

    如何实现一个堆?

    要实现一个堆,我们先要知道,堆都支持哪些操作以及如何存储一个堆

    完全二叉树适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组下标,就可以找到一个节点的左右子节点和父节点。在这里插入图片描述

    从上图中可以看出,数组下标为 i 的节点的左子节点,就是下标为 i2的节点,右子节点就是下标为 i2+1 的节点,父节点不是下标为 i/2 的节点。

    知道了如何存储一个堆,那我们再来看看,堆上的操作有哪些?我罗列了几个非常核心的操作,分别是往堆中插入一个元素和删除堆顶元素。(如果没有特殊说明,我下面都是拿大顶堆来讲解)。

    1、往堆中插入一个元素

    往堆中插入一个元素后,我们需要满足堆的两个特性。

    如果我们把新插入的元素放到堆的最后,如下图,是不符合堆的特性的。还需要调整,让其重新满足堆的特性。这个过程就叫作堆化(heapify)。堆化分为两种,从下往上和从上往下。先说从下往上的堆化方法。在这里插入图片描述

    堆化非常简单,就是顺着节点所在的考核体系,向上或者躺下,对比,然后交换。

    如下面的分解图,我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系,我们就互换两个节点。一直重复这个过程,直到父子节点之间满足刚说的那种大小关系。代码实现如下:在这里插入图片描述

    	public class Heap{
    		private int[] a; //数组,从下标1开始存储数据
    		
    		private int n; // 堆可以存储的最大数据个数
    		
    		private int count; // 堆中已经存储的数据个数
    		
    		public Heap(int capacity) {
    			a = new int[capacity + 1];
    			n = capacity;
    			count = 0;
    		}
    		
    		public void insert(int data) {
    			if(count >= n) {
    				return; // 没有空间了
    			}
    			++count;
    			a[count] = data;
    			int i = count;
    			while(i/2 > 0 && a[i] > a[i/2]) {
    				int temp = a[i];
    				a[i] = a[i/2];
    				a[1/2] = temp;
    				i = i/2;
    			}
    		}
    	}
    

    2、删除堆顶元素

    从堆的定义的第二条中,任何节点的值都大于等于(或小于等于)子树节点的值,我们可以发现,堆顶元素存储的就是堆中数据的最大值或者最小值。

    假设我们构造的是大顶堆,堆顶元素就是最大的元素。当我们删除堆顶元素之后,就需要把第二大的元素放到堆顶,那第二大元素肯定会出现在左右节点中。然后我们再迭代地删除第二大节点,以此类推,直到叶子节点被删除。

    这里我也画了一个分解图。不过这种方法有点问题,就是最后出来的堆并不满足完全二叉树的特性在这里插入图片描述

    实际上,我们稍微改变一下思路,就可以解决这个问题。我们把最后一个节点放到堆顶,然后利用同样的父子节点对比方法。对于不满足父子节点大小关系的,互换两个节点,并且重复这个过程,直到父子节点之间满足大小关系为止。这就是从上往下的堆化方法。

    因为我们移除的是数组中的最后一个元素,而在堆化的过程中,都是交换操作,不会出现数组中“空洞”,所以这种方法堆化之后的结果,肯定满足完全二叉树的特性。
    在这里插入图片描述

    		public void removeMax() {
    			if (count == 0) {
    				return;
    			}
    			a[1] = a[count];
    			--count;
    			heapify(a, count, 1);
    		}
    
    		private void heapify(int[] a, int n, int i) { // 自上往下堆化
    			while (true) {
    				int maxPos = i;
    				if (i * 2 <= n && a[i] < a[i * 2]) {
    					maxPos = i * 2;
    				}
    				if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
    					maxPos = i * 2 + 1;
    				}
    				if(maxPos == i) {
    					break;
    				}
    				int tem = a[i];
    				a[i] = a[maxPos];
    				a[maxPos] = tem;
    				i = maxPos;
    			}
    		}
    

    堆化的过程虽顺着节点所在的路径比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是O(logn)。插入数据和删除堆顶元素的主要逻辑就是堆化,所以往堆中插入一个元素和删除堆元素的时间复杂度都是O(logn)。

    如何基于堆实现排序?

    前面我们讲过好几种排序算法,有时间复杂度是(O2)的冒泡、插入、选择排序,有时间复杂度是O(nlogn)的归并、快速、线性排序。

    借助于堆这种数据结构实现的排序算法,就叫做堆排序。这种排序算法的时间复杂度非常稳定,是O(nlogn),并且它还是原地排序算法,如此优秀,这是怎么做到的呢?

    可以把堆排序的过程大致分解成两大步骤,建堆排序

    1、建堆

    首先将数组原地建成一个堆。所谓“原地”就是,不借助另一个数组,就在原数组上操作。建堆的过程,有两种思路。

    第一种是借助我们前面讲的,在堆中插入一个元素的思路。尽管数组中包含 n 个数据,但是我们可以假设,起初堆中只包含一个数据,就是下标为1的数据。然后,我们调用前面的插入操作,将下标从2到 n 的数据依次插入到堆中。这样我们就将包含n 个数据数组组织成了堆。

    第二种实现思路,跟第一种截然相反。第一种思路的处理过程是从前往后处理数据,并且每个数据插入堆中时,都是从下往上的堆化。而第二种实现的思路,是从后往前处理数组,并且每个数据都是从上往下堆化。

    如下图,因为叶子往下堆化只能自己跟自己比较,所以我们直接从第一个非叶子节点开始,依次堆化就行了。在这里插入图片描述

    		public void buildHeap(int[]a, int n) {
    			for(int i = n/2; i >= 1; --i) {
    				heapify(a, n, i);
    			}
    		}
    

    上面的代码中,我们对下标从 n/2 开始到 1 的数据进行堆化,下标是 n/2+1 到 n 的节点是叶子节点,我们不需要堆化。实际上,对于完全二叉树来说,下标从n/2+1 到 n的节点都是叶子节点。

    建堆操作的时间复杂度是多少呢?

    每个节点堆化的时间复杂度是O(logn),那 n/2+1 个节点堆化的总时间复杂度是不是就是O(nlogn)呢?这个答案虽然也没错,但这个值不够精确。实际上,堆排序的建堆过程时间复杂度是O(n)。

    因为叶子节点是不需要堆化的,所以需要堆化的节点从倒数第二层开始。每个节点堆化的过程中,需要比较和交换的节点个数,跟这个节点的高度 k 成正比。看下图在这里插入图片描述

    我们将每个非叶子节点的高度求和,就是下面的公式:
    在这里插入图片描述
    在这里插入图片描述

    最后再把 2h= n 代入,可得建堆的时间复杂充就是O(n)。

    2、排序

    建堆结束之后,数组中的数据已经是执照大顶堆的特性来组织的。数组中的第一个元素就是堆顶,也就是最大的元素。我们把它跟最后一个元素交换,那最大的元素就放到了下标为 n 的位置。

    这个过程有点类似上面讲的“删除堆顶元素”的操作,当堆顶元素移除之后,我们把下标为 n 的元素放到堆顶,然后再通过堆化的方法,将剩下的 n-1 个元素重新构建成堆。堆化完成之后,我们再取堆顶元素,放到下标是 n-1 的位置,一直重复这个过程,直到最后堆中只剩下为1个元素,排序工作就完成了。在这里插入图片描述

    		public void sort(int[]a, int n) {
    			buildHeap(a, n);
    			int k = n;
    			while( k > 1) {
    				int temp = a[k];
    				a[k] = a[1];
    				a[1] = temp;
    				--k;
    				heapify(a, k, 1);
    			}
    		}
    

    整个堆排序的过程,都只需要极个别的临时存储空间,所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是O(n),排序过程的时间复杂度是O(nlogn),所以,堆排序整体的时间复杂度是O(nlogn)。

    堆排序是不稳定的排序算法,因为排序的过程,存在的最后一个节点跟堆项节点互换的操作,所以就有可能改变值相等数据的原始相对顺序。

    解答开篇

    现在,我们来看下,实际开发中,为什么快速排序要比堆排序性能好?

    第一、堆排序访问数据的方式没有快速排序友好。

    对于快速排序来说,数据是顺序访问的。而对于堆排序来说,数据是跳着访问的。比如,堆排序中,最重要的一个操作就是数据的堆化。比如下面这个例子,对堆顶进行堆化,会依次访问数组下标是1,2,4,8的元素,而不像快速排序那样,局部顺序访问,所以,这样对CPU缓存是不友好的。
    在这里插入图片描述

    第二、对于同样的数据,在排序过程中,堆排序算法的数据交换次数要多于快速排序。

    我们在讲排序的时候,提过两个概念,有序度和逆序度。对于基于比较的排序算法来说,整个排序过程是由两个基本操作组成的,比较和交换。快速排序交换的次数不会比逆序度多。

    但是堆排序的第一步是建堆,建堆的过程会打乱数据原有的相对选择顺序,导致数据有序度降低。比如对于一组已经有序的数据来说,经过建堆之后,数据反而变得更无序了。在这里插入图片描述

    展开全文
  • 最大堆和堆排序学习笔记

    千次阅读 2016-08-17 16:40:28
    今天学习最大堆和堆排序。 最大(小)堆: 实质:逻辑结构:完全二叉树;存储结构:数组。(参考这篇文章,详细讲述了二叉树的存储结构http://www.cnblogs.com/pengyingh/articles/2396466.html); 特点:最大堆...

    最近要准备面试,补习数据结构和算法(都是泪),在这里做一个学习笔记。
    今天学习最大堆和堆排序。
    最大(小)堆:
    实质:逻辑结构:完全二叉树;存储结构:数组。(参考这篇文章,详细讲述了二叉树的存储结构http://www.cnblogs.com/pengyingh/articles/2396466.html);
    特点:最大堆的父亲要大于等于孩子。(最小堆相反);

    堆排序:一种选择排序,每次在序列中取出最大值或最小值,相比直接选择排序,堆排序体现出了数据结构的好处。
    原理:利用构建的最大堆的性质,每次最大堆的堆顶元素,将堆顶元素放到堆尾,即将数组的第一个元素和最后一个元素交换;再对剩下的N-1个元素循环操作,边排序完毕;
    时间复杂度:O(nlogn);(构建堆需要logn,堆排序需要n次构建);
    空间复杂度:O(1);只需要一个常量单元用于交换。
    堆排序不适合排序小数据量;频繁建堆。

    代码实现

    #include <iostream>
    using namespace std;
    
    int parent(int i)//数组存储结构,完全二叉树
    {
       return i/2;
    }
    
    int left(int i)
    {
        return i*2;
    }
    int right(int i)
    {
        return i*2+1;
    }
    
    
    void maxheap(int *a,int i,int length)
    {
        int L,R;
        L=left(i);
        R=right(i);
        int largest;
        if (L<length&&a[L-1]>a[i-1])
        {
            largest=L;
        }
        else
        {
            largest=i;
        }
        if (R<length&&a[R-1]>a[largest-1])
        {
            largest=R;
        }
        if (largest!=i)
        {
            int temp;
            temp=a[i-1];
            a[i-1]=a[largest-1];
            a[largest-1]=temp;
            maxheap(a,largest,length);//每次交换后,都需要对交换的孩子节点再次构建最大堆
        }
    
    
    }
    void Max_heap(int *a,int length)
    {
        if (length>1)
        {
            for (int i=length/2;i>0;i--)
            {
                maxheap(a,i,length);
            }
    
        }
    
    }
    
    
    void heap_sort(int *a,int length)
    {
        if (length > 1)
        {
            for (int i=length;i>1;i--)
            {
                Max_heap(a,i);
                int temp;
                temp=a[0];
                a[0]=a[i-1];
                a[i-1]=temp;
            }
        }
    
    }
    void main()
    {
        int a[10]={5,3,5,8,2,9,12,78,9,2};
        //Max_heap(a,10);
        heap_sort(a,10);
        for (int i=0;i<10;i++)
        {
            cout<<a[i]<<endl;
        }
    }
    展开全文
  • python实现最大堆,最小堆和堆排序

    千次阅读 2019-04-13 22:35:00
    3.堆排序 0.什么是堆 小堆大堆分为如下图: 堆需要满足的条件: 1. 必须是二叉树,且必须是完全二叉树 2. 各个父节点必须大于或小于左右结点, 其中最顶层的根结点必须是最大或者最小的 堆可以使用list...
  • Java排序算法--建立堆和堆排序(练习)

    千次阅读 2016-09-23 11:28:08
    堆排序的思想:循环建立堆,然后交换角标0的节点角标最后的节点。即排序由两部分组成,建立堆的渗透函数,通过循环调用渗透函数 堆排序是一种树形选择排序,是对直接选择排序的有效改进。 堆的定义如下:具有...
  • 普通队列:先进先出,后进后出 优先队列:出队顺序入队顺序无关,优先级有关 例如:在N个元素中选择前M个元素,用排序的方法复杂度为NlogN,而使用则为NlogM ...
  • 堆这种数据结构的应用场景非常多,最经典的莫过于堆排序了。堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。 1. 什么是堆 堆是一个完全二叉树; 堆中每一个节点的值都必须大于等于(或小于等于)其子树...
  • 所谓堆和堆排序

    千次阅读 2009-09-22 22:44:00
    ,是一棵完全二叉树,根的值大于左右子树中所有结点的值,左右子树也是,除此之外,对其它元素之间的大小关系(如左右子树之间元素大小关系)没有要求。 这是大根,如果把“大于”换成“小于”,就是小根,...
  • 堆排序算法(图解详细流程)

    万次阅读 多人点赞 2018-08-04 11:21:17
    堆排序的时间复杂度O(N*logN),额外空间复杂度O(1),是一个不...堆的结构可以分为大根堆小根堆,是一个完全二叉树,而堆排序是根据堆的这种数据结构设计的一种排序,下面先来看看什么是大根堆小根堆 1.1 大根...
  • 堆排序堆排序优化、索引堆排序(稳定排序) 1、堆: 所有元素 都从索引0开始 父亲结点索引:i; 左孩子结点索引: 2*i+1; 右孩子结点索引: 2*i+2; 左后一个非叶子结点索引:(n-1)/2; 用于构建堆,从...
  • 算法 - 堆排序(C#)

    万次阅读 多人点赞 2019-02-01 15:34:50
    * 堆排序是一种选择排序,时间复杂度为O(nlog&lt;sub&gt;2&lt;/sub&gt;n)。 * * 堆排序的特点是: * 在排序过程中,将待排序数组看成是一棵完全二叉树的顺序存储结构, * 利用完全二叉树中父...
  • 堆排序

    千次阅读 多人点赞 2021-02-12 12:53:05
    堆排序 堆排序顾名思义,就是使用堆这种数据结构进行排序,什么是堆呢,堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。 堆总是满足下列性质: 堆中某个结点的...
  • 高人能不能讲述一下初始堆和堆排序的区别是什么呀? 首先建立完全二叉树 45 28 49 16 37 82 56 75 从n/2个节点开始选择,第一趟,16比75小,不换.到n/2-1个节点,4982、56比,49小,也不换.到n/2-2个结点,2816、...
  • 堆和堆的应用:堆排序和优先队列

    千次阅读 2017-11-19 11:57:02
    堆和堆的应用堆排序和优先队列 堆 堆的应用堆排序 堆的应用优先队列 堆的应用海量实数中一亿级别以上找到TopK一万级别以下的数集合 总结 references堆和堆的应用:堆排序和优先队列1.堆堆(Heap)是一种重要的数据结构...
  • 堆排序和归并排序

    千次阅读 2017-08-15 11:05:57
    一、堆排序 1.1 简介 堆排序与快速排序,归并排序一样都是时间复杂度为O(n*logn)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的堆。 堆的定义:n个元素的序列{k1,k2,…,kn}当且仅当满足下列...
  • 堆排序定义: 堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆小根堆,是完全二叉树。 满二叉树定义: ...
  • 开门见山,本文讲述堆排序。 就我自身对于排序的了解来看,其实堆排序是诸多排序中最难写的,光是理解起来都有点费劲,本文旨在于用通俗易懂的话,把堆排序娓娓道来。 下面,开始! 1:堆 毫无疑问,排序两个字...
  • 排序——堆排序和TopK

    千次阅读 2019-04-02 10:56:54
    堆排序与TopK的问题,面试中还是经常问的,索性也整理一下。下面是徒手写的,供参考. 堆排序 public void heapSort(int[] array) { // 先构造一个大顶堆 int N = array.length - 1; for (int i = (N - 1) / 2; i ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 292,019
精华内容 116,807
关键字:

堆和堆排序