java实现堆排序（2016年腾讯内推笔试的一道算法题）

65 阅读 0 评论 43 点赞

我是靠谱客的博主谨慎茉莉，最近开发中收集的这篇文章主要介绍java实现堆排序（2016年腾讯内推笔试的一道算法题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/**这是2016年腾讯微信部web开发内推笔试的一道题
 * 题目情景：有一个公司有若干员工，要求设计一个签到系统来记录员工的签到顺序，
 *          并能够在nlogn的时间复杂度内利用尽可能少的辅助空间将签到的员工按照员工id进行排序。
 * 思路：在所有算法中只有堆排序和归并排序能够达到时间复杂度的要求，而堆排序对空间的要求
 *       又要优于归并排序，所以最后采用了堆排序来实现。*/

/*构建员工模型*/
class Staff{
	int id;//员工id
	Staff(int id ){
		this.id=id;
	}
	public void setId(int id){
		this.id=id;
	}
	public int getId(){
		return this.id;
	}
	
}
public class StaffSort {
	private Staff[] log; // 记录员工序号序列
	private int totalStaff; // 员工总人数
	private int currentStaff; //此时员工人数

	public StaffSort(int totalStaff) {
		// TODO Auto-generated constructor stub
		this.totalStaff=totalStaff;
		currentStaff=0;
		log=new Staff[totalStaff];
	}

	/*
	 * @author Sam
	 * @param id
	 * @return isSuccess
	 * Described 员工签到*/
	public boolean check(int id) {
		Staff newStaff = new Staff(id);
		log[currentStaff] = newStaff;
		trickleUp(currentStaff++);
		return true;
	}

	/*
	 * @author Sam
	 * @param index
	 * @return isSuccess
	 * Described 向上调整堆模型，使各点的值不大于其双亲结点的值*/
	public void trickleUp(int index) {
		int parent = (index - 1) / 2;
		Staff bottom = log[index];

		while (index > 0 && log[parent].getId() < bottom.getId()) {
			log[index] = log[parent]; 
			index = parent;
			parent = (parent - 1) / 2;
		}
		log[index] = bottom; 
	}

	/*
	 * @author Sam
	 * @param 
	 * @return root
	 * Described 获取并删除堆顶*/
	public Staff remove() {
		Staff root = log[0];
		log[0] = log[--currentStaff];
		trickleDown(0);
		return root;
	}

	/*
	 * @author Sam
	 * @param index
	 * @return 
	 * Described 向下调整堆结构，是堆顶元素不小于孩子结点的值*/
	public void trickleDown(int index) {
		int largeChild;
		Staff top = log[index]; 
		while (index < currentStaff / 2) { 
			int leftChild = 2 * index + 1;
			int rightChild = leftChild + 1;

			if (rightChild < currentStaff
					&& log[leftChild].getId() < log[rightChild]
							.getId()) {
				largeChild = rightChild;
			} else {
				largeChild = leftChild;
			}

			if (top.getId() >= log[largeChild].getId()) {
				break;
			}

			log[index] = log[largeChild]; 
			index = largeChild; 
		}
		log[index] = top;
	}

	/*
	 * @author Sam
	 * @param args
	 * @return 
	 * Described 打印排序后的结果*/
	public static void main(String[]args){
		int[] staffs=new int[]{1,3,5,2,12,10,15};
		StaffSort ss=new StaffSort(50);
		for(int i=0;i<staffs.length;i++){
			ss.check(staffs[i]);
		}
		while (ss.currentStaff!=0) {
			System.out.print(ss.remove().getId()+" ");
			
		}
	}

}