欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构 - 堆排序

程序员文章站 2022-06-04 09:12:46
...

1、题目描述

输入一个长度为n的整数数列,从小到大输出前m小的数。

输入格式

第一行包含整数n和m。

第二行包含n个整数,表示整数数列。

输出格式

共一行,包含m个整数,表示整数数列中前m小的数。

数据范围

1≤m≤n≤1051≤m≤n≤105,
1≤数列中元素≤1091≤数列中元素≤109

输入样例:

5 3
4 5 1 3 2

输出样例:

1 2 3

 

2、 分析

数据结构 - 堆排序

数据结构 - 堆排序

 

以小根堆为例,建堆:

/**
         * 建小顶堆:从最后一个非叶子结点开始,往前,直到根节点
         */
        for(int i = n / 2;i >= 1;i --){
            down(i);
        }

i为什么从n/2开始down?

首先要明确要进行down操作时必须满足左儿子和右儿子已经是个堆。

开始创建堆的时候,元素是随机插入的,所以不能从根节点开始down,而是要找到满足下面三个性质的结点:

1.左右儿子满足堆的性质。

2.下标最大(因为要往上遍历)

3.不是叶结点(叶节点一定满足堆的性质)

 

数据结构 - 堆排序

 

3、代码


import java.io.InputStreamReader;
import java.util.Scanner;

/**
 * 堆:是一棵完全二叉树
 * 设堆顶下标为x,则堆顶的左孩子:2*x,堆顶的右孩子:2*x+1
 * 
 * @author zhou
 *
 */
public class Main {
	static int N = 100010;
	static int[] heap = new int[N];
	static int size; //表示堆的大小
	
	public static void main(String[] args) {
		Scanner in = new Scanner(new InputStreamReader(System.in));
		int n = in.nextInt();
		int m = in.nextInt();
		
		for(int i = 1;i <= n;i ++){
			heap[i] = in.nextInt();
		}
		size = n;
		
		/**
		 * 建小顶堆:从最后一个非叶子结点开始,往前,直到根节点
		 */
		for(int i = n / 2;i >= 1;i --){
			down(i);
		}
		
		while(m-- > 0){
			//输出堆顶元素
			System.out.print(heap[1] + " ");
			//删除堆顶元素,再重新建堆
			heap[1] = heap[size];
			size --;
			down(1);
		}
	}

	//down操作的是堆的下标,因为需要用到 堆顶的左孩子:2*x,堆顶的右孩子:2*x+1
	private static void down(int idx) {
		int t = idx; //t保存结点值最小的那个下标
		if(2*idx <= size && (heap[2*idx] < heap[t])){
			t = 2*idx;
		}
		if(2*idx+1 <= size && (heap[2*idx+1] < heap[t])){
			t = 2*idx+1;
		}
		if(idx != t){	
			int tmp = heap[idx];
			heap[idx] = heap[t];
			heap[t] = tmp;
			down(t);
		}
	}

}

数据结构 - 堆排序