必威体育Betway必威体育官网
当前位置:首页 > IT技术

八大排序算法--堆排序

时间:2019-10-09 08:44:35来源:IT技术作者:seo实验室小编阅读:58次「手机版」
 

堆排序算法

序言

对于堆排序的学习,实际上就是对于 这一种数据结构的学习,把堆学会了,堆排序自然也就学会了。

1、为什么使用堆这种数据结构

优先队列是一种很常用的队列,比如在游戏中,游戏角色在自动模式下,如何在周围一堆小怪中自动攻击某一个小怪?可能是判断这一群小怪哪一个比较近,就攻击哪一个,或者哪一个等级低,就攻击哪一个。总之,是会动态的计算周围小怪的优先级,然后攻击优先级最高的那一个小怪。

堆 这一种数据结构,就是典型的动态优先队列。

另外,如果要从1000000个元素中选出排序前100的元素,如何选出来呢?从N个元素中取出前M个元素?如果用前面介绍到的算法,只能先排序(时间复杂度为NlogN),然后取出前一百元素,如果使用堆排序,那么时间复杂度将降为NlogM. 时间效率将极大提升。

2、堆的定义以及堆的数据模型

堆的典型数据模型就是一个二叉堆, 如下图,是一个最大二叉堆:

在这里插入图片描述

最大二叉堆的定义:

  • 1、最顶端的肯定是最大的值
  • 2、父节点的值总是大于子节点的值。
  • 3、是一个完全二叉树,它的层高相差不超过1,叶子结点总是从左向右依次填满。

相应的,如果根节点是最小值,就是最小二叉堆。只要满足上面三个条件即可,在上图中,13的层级比17要高一层,这并没有违反规则,是可以的。

3、堆的基本存储

我们使用堆的规则,将数据存储在数组中。

在这里插入图片描述

如上图,是一个堆的示例,在数组中,我们从角标为1的位置开始存放数据,角标0我们并不使用。然后从上往下编号, 最大的数排第一个,然后往下一层从左到右依次排序,我们可以发现,如果父节点的位置是第i个,那么左节点就会是第2i个,右节点是第2i+1个。而子节点如果是第i个,则父节点就是第 i/2 个(如果有父节点)。这个规则很重要,下面写代码将用到。

3.1 数据的添加

我们明白了这个规则,就可以进行数据的插入了。在堆中添加一个元素,相当于在数组的末尾添加了一个元素,这个元素的位置暂时是最后一个,然后判断是否满足最大堆的定义,如果它比父节点要大,则需要把这个数和父节点交换。交换以后,如果在当前位置还要比父节点大,则继续向上交换,直到合适的位置,所以我们需要定义一个向上移动的函数shiftUp();

public void insert(Item item) {
	if(count == capcity) {
		return;//已经填满了,无法再填入数据了
	}
	data[count+1] = item;
	count ++;//记录总共有多少个数据
	ShiftUp(count);//执行向上移动
}

/**
 * 将k这个位置的元素 调整到堆的合适位置,
 * 
 * 最大堆的特点,父节点大于子节点
 * 完全二叉树特点,总是从左到右,依次填满二叉树的子节点
 */
private void ShiftUp(int k) {
	//用数组存储完全二叉堆,如果根节点的序列化声明为1,则左节点的序号都是父节点的二倍,看图理解,右节点是父节点的二倍+1
	//父节点如果小于子节点,就要交换位置, 注意边界问题,所以k>1
	while(k > 1 && data[k/2].compareTo(data[k]) < 0) {
		swap( k, k/2);
		k /= 2;
	}
}

/**
 * 交换数组中两个值的位置
 */
private void swap(int i, int j) {
	Item temp = data[i];
	data[i] = data[j];
	data[j] = temp;
}

3.2 最大数据的取出(数据的删除)

我们刚刚说了,这是一个优先级队列,当需要取出优先级最高的数时,即需要取出二叉堆最顶端的数时,我们通常的操作就是将最顶端(脚标为1的数)和数组中最后一个数交换位置,然后移除左后一个元素即可。但是,此时,就不满足最顶端的数时最大数这个规则了,因此此时需要把顶端这个数向下移动(shiftDown), 它需要和左右两个孩子比较,和最大的孩子进行交换,如果交换位置后,它的子孩子还要大于它,则继续和左右孩子中的最大值进行交换,直到移动到合适位置。

/**
 * 取出最大元素
 */
public Item extractMax() {
	if(count == 0) {
		return null;
	}
	Item item = data[1];//堆中第一个元素就是最大值
	swap(1, count);//将最后一个元素放到第一个位置
	count --;//总的数量减一
	shiftDown(1);//重新调整整个堆,成为一个新的最大二叉堆
	return item;
}


/**
 * 将元素向下移动,直到找到合适的位置
 */
private void shiftDown(int i) {
	while(i*2 <= count) {//说明有左孩子
		int j = i*2;//左孩子的脚标位置
		if(j+1 <= count && data[j+1].compareTo(data[j]) > 0) {
			//如果有右孩子,并且,右孩子比左孩子的值大
			j = j+1;
		}
		if(data[i].compareTo(data[j]) > 0) {
			break;//如果父节点大于 最大的子节点,则已经是新的最大二叉堆
		}
		swap(i, j);//否则,则交换父节点和最大子节点的位置,继续向下比较
		i = j;//更新这个值的最新位置
	}
	
}

如果我们循环调用此函数,依次取出最大值,则就完成了优先级从最高到最低的排序。

3.3 堆化(Heapify)

如果我们传入一个整个数组,数组中有一系列数据,那么我们就可以将这个数组形成一个堆的结构,这个过程称为堆化(Heapify)。

传入整个数组Heapify的算法复杂度比直接一个一个插入数据的效率更高

将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn)
heapify的过程,算法复杂度为O(n),即在一个已知数组上去进行优先级排序,会更快。 具体的证明可以网上找

就算不证明,想一下也会快一点,用heapify,每次n/2,直接减少一半的数据,所以快很多

在这里插入图片描述

通过观察可以得到,count/2得到的节点为最后一个父节点(非叶子节点), 然后它的角标依次减减, 就得到其他的父节点,依次调整每个父节点的子树为一个完全二叉堆,最后就得到一颗新的完全二叉堆树。

public MaxHeap(Item[] arr) {
	this.capcity = arr.length;
	//warnningValue = (n * 10) / 9;
	data = (Item[]) new Comparable[capcity + 1];
	System.arraycopy(arr, 0, data, 1, arr.length);
	count = arr.length;
	
	for(int i = count/2; i >= 1; i --) {
		shiftDown(i);
	}
}

3.4 时间复杂度比较

使用堆排序和使用普通数组的时间复杂度比较

验证结果输出

The max heap size is: 12
Data in the max heap(注意这不是排序,只是数据在堆中的位置): 
84 65 65 64 54 14 16 10 57 27 25 9 

           84          
      /          \     
     65          65    
   /    \      /    \  
  64    54    14    16 
 / \   / \   / \   / \ 
10 57 27 25 9          
max=84
The max heap size is: 11
Data in the max heap(注意这不是排序,只是数据在堆中的位置): 
65 64 65 57 54 14 16 10 9 27 25 

           65          
      /          \     
     64          65    
   /    \      /    \  
  57    54    14    16 
 / \   / \   / \   / \ 
10  9 27 25            
排序结果: 65  65  64  57  54  27  25  16  14  10  9       

完整代码

功能验证可以使用printMaxHeap类,它会在控制台打印输出排序完成后的数组的数据,以及整个堆的结构, 完整功能及测试代码如下:

最大堆 MaxHeap:

import java.util.Arrays;

/**
 * 最大堆, 此处使用了泛型,
 * @author admin
 *
 */
public class MaxHeap<Item extends Comparable> {
	protected Item[] data;
	protected int count;
	private int capcity;
	private int warnningValue;
	private byte[] lock = new byte[0];
	
	public MaxHeap(int capcity){
		
		this.capcity = capcity;
		warnningValue = (capcity * 10) / 9;
		//java不允许直接创建泛型数组,否则编译报错,所以通过强转来通过编译
		//第0个位置不存储,从第一个位置开始存储,所以空一个位置
		data= (Item[]) new Comparable[capcity+1];
		count = 0;
		
	}
	
	public MaxHeap(Item[] arr) {
		this.capcity = arr.length;
//		warnningValue = (n * 10) / 9;
		data = (Item[]) new Comparable[capcity + 1];
		System.arraycopy(arr, 0, data, 1, arr.length);
		count = arr.length;
		
		for(int i = count/2; i >= 1; i --) {
			shiftDown(i);
		}
	}
	
	public int size() {
		return count;
	}
	
	public boolean isempty() {
		return count == 0;
	}
	
	public void destory() {
		data = null;
		count = 0;
	}
	

	//此方法可以学习时可以忽略,是insert方法的改良版, 参考了ArrayList插入数据的扩容功能。
	public void insert2(Item item) {
		//如果数量大于警戒值了,就是快要满了,此时扩容,考虑到多线程,没有使用 == capcity来判断
		if(count >= warnningValue) {
			synchronized (lock) {
				if(count >= warnningValue) {
					capcity = capcity * 2;
					warnningValue = (capcity * 10) / 9;
					//第0个位置不存储,从第一个位置开始存储,所以空一个位置
					Item[] temp = (Item[]) new Comparable[capcity+1];
					//方法二: System.arraycopy(src, srcPos, dest, destPos, length)
			    	//src: 源数组
			    	//srcPos: 从源数组复制数据的起始位置
			    	//dest: 目标数组
			    	//destPos: 复制到目标数组的起始位置
					//length:数组的元素个数
					System.arraycopy(data, 0, temp, 0, data.length);
					data = temp;
				}
			}
		}
		data[count+1] = item;
		count ++;
		ShiftUp(count);
	}
	
	public void insert(Item item) {
		if(count == capcity) {
			return;//已经填满了,无法再填入数据了
		}
		data[count+1] = item;
		count ++;
		ShiftUp(count);
	}
	
	/**
	 * 取出最大元素
	 */
	public Item extractMax() {
		if(count == 0) {
			return null;
		}
		Item item = data[1];//堆中第一个元素就是最大值
		swap(1, count);//将最后一个元素放到第一个位置
		count --;//总的数量减一
		shiftDown(1);//重新调整整个堆,成为一个新的最大二叉堆
		return item;
	}
	
	/**
	 * 将元素向下移动,直到找到合适的位置
	 */
	private void shiftDown(int i) {
		while(i*2 <= count) {//说明有左孩子
			int j = i*2;//左孩子的脚标位置
			if(j+1 <= count && data[j+1].compareTo(data[j]) > 0) {
				//如果有右孩子,并且,右孩子比左孩子的值大
				j = j+1;
			}
			if(data[i].compareTo(data[j]) > 0) {
				break;//如果父节点大于 最大的子节点,则已经是新的最大二叉堆
			}
			swap(i, j);//否则,则交换父节点和最大子节点的位置,继续向下比较
			i = j;//更新这个值的最新位置
		}
		
	}

	/**
	 * 将k这个位置的元素 调整到堆的合适位置,
	 * 
	 * 最大堆的特点,父节点大于子节点
	 * 完全二叉树特点,总是从左到右,依次填满二叉树的子节点
	 */
	private void ShiftUp(int k) {
		//用数组存储完全二叉堆,如果根节点的序列化声明为1,则左节点的序号都是父节点的二倍,看图理解,右节点是父节点的二倍+1
		//父节点如果小于子节点,就要交换位置, 注意边界问题,所以k>1
		while(k > 1 && data[k/2].compareTo(data[k]) < 0) {
			swap( k, k/2);
			k /= 2;
		}
	}
	
	/**
	 * 交换数组中两个值的位置
	 */
	private void swap(int i, int j) {
		Item temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

}

功能测试类(测试类只关注功能测试即可,打印堆的方法不用去关注,不是本文重点):

public class PrintMaxHeap extends MaxHeap<Comparable<integer>> {

	public PrintMaxHeap(int capacity) {
		super(capacity);
	}
	
	public PrintMaxHeap(Comparable[] arr) {
		super(arr);
	}
	
	// 测试 PrintableMaxHeap
    public static void main(String[] args) {
    	testMaxHeap1() ;
    	//testMaxHeap2() ;
    }
    
    public static void testMaxHeap1() {

    	PrintMaxHeap maxHeap = new PrintMaxHeap(100);
        int N = 12; // 堆中元素个数
        int M = 90; // 堆中元素取值范围[0, M)
        for( int i = 0 ; i < N ; i ++ )
            maxHeap.insert( new Integer((int)(Math.random() * M)) );
        maxHeap.treePrint();
        Comparable i = maxHeap.extractMax();
        System.out.println("max="+i);
        maxHeap.treePrint();
    }
    public static void testMaxHeap2() {

    	PrintMaxHeap maxHeap = new PrintMaxHeap(randomArray(12));
        maxHeap.treePrint();
        Comparable i = maxHeap.extractMax();
        System.out.println("max="+i);
        maxHeap.treePrint();
    }

	
	// 以树状打印整个堆结构
    public void treePrint(){

        if( size() >= 100 ){
            System.out.println("This print function can only work for less than 100 integer");
            return;
        }

        System.out.println("The max heap size is: " + size());
        System.out.println("Data in the max heap: ");
        for( int i = 1 ; i <= size() ; i ++ ){
            // 我们的print函数要求堆中的所有整数在[0, 100)的范围内
            assert (Integer)data[i] >= 0 && (Integer)data[i] < 100;
            System.out.print(data[i] + " ");
        }
        System.out.println();
        System.out.println();

        int n = size();
        int maxLevel = 0;
        int numberPerLevel = 1;
        while( n > 0 ){
            maxLevel += 1;
            n -= numberPerLevel;
            numberPerLevel *= 2;
        }

        int maxLevelNumber = (int)Math.pow(2, maxLevel-1);
        int curTreeMaxLevelNumber = maxLevelNumber;
        int index = 1;
        for( int level = 0 ; level < maxLevel ; level ++ ){

            String line1 = new String(new char[maxLevelNumber*3-1]).replace('\0', ' ');

            int curLevelNumber = Math.min(count-(int)Math.pow(2,level)+1,(int)Math.pow(2,level));
            boolean isLeft = true;
            for( int indexCurLevel = 0 ; indexCurLevel < curLevelNumber ; index ++ , indexCurLevel ++ ){
                line1 = putNumberinline( (Integer)data[index] , line1 , indexCurLevel , curTreeMaxLevelNumber*3-1 , isLeft );
                isLeft = !isLeft;
            }
            System.out.println(line1);

            if( level == maxLevel - 1 )
                break;

            String line2 = new String(new char[maxLevelNumber*3-1]).replace('\0', ' ');
            for( int indexCurLevel = 0 ; indexCurLevel < curLevelNumber ; indexCurLevel ++ )
                line2 = putBranchInLine( line2 , indexCurLevel , curTreeMaxLevelNumber*3-1 );
            System.out.println(line2);

            curTreeMaxLevelNumber /= 2;
        }
    }
    
    private String putNumberInLine( Integer num, String line, int indexCurLevel, int curTreeWidth, boolean isLeft){

        int subTreeWidth = (curTreeWidth - 1) / 2;
        int offset = indexCurLevel * (curTreeWidth+1) + subTreeWidth;
        assert offset + 1 < line.length();
        if( num >= 10 )
            line = line.substring(0, offset+0) + num.toString()
                    + line.substring(offset+2);
        else{
            if( isLeft)
                line = line.substring(0, offset+0) + num.toString()
                        + line.substring(offset+1);
            else
                line = line.substring(0, offset+1) + num.toString()
                        + line.substring(offset+2);
        }
        return line;
    }

    private String putBranchInLine( String line, int indexCurLevel, int curTreeWidth){

        int subTreeWidth = (curTreeWidth - 1) / 2;
        int subSubTreeWidth = (subTreeWidth - 1) / 2;
        int offsetleft = indexCurLevel * (curTreeWidth+1) + subSubTreeWidth;
        assert offsetLeft + 1 < line.length();
        int offsetRight = indexCurLevel * (curTreeWidth+1) + subTreeWidth + 1 + subSubTreeWidth;
        assert offsetRight < line.length();

        line = line.substring(0, offsetLeft+1) + "/" + line.substring(offsetLeft+2);
        line = line.substring(0, offsetRight) + "\\" + line.substring(offsetRight+1);

        return line;
    }
    
	public static Integer[] randomArray(int length) {
		Integer[] arr = new Integer[length];
		Random random = new Random();
		for(int i=0; i<length; i++) {
			arr[i] = random.nextint(100);
		}
		//自动生成随机数组,先进行一次原始数据打印
		System.out.println(Arrays.toString(arr));
		return arr;
	}

}

相关阅读

堆排序算法详解

一、堆排序算法原理和动态图解 将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将它移走(其实就是将

选择排序(简单选择排序和堆排序)

选择排序的基本思想是:每一趟(例如第i趟)在后面的 n-i+1 个待排序元素中选取关键字最小的元素,作为有序子序列的第i个元素,直到第 n-1

排序算法之堆排序(Heap Sort)——C语言实现

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。 算法分析 在学习堆排序之前我们要先

分享到:

栏目导航

推荐阅读

热门阅读