本文共 5438 字,大约阅读时间需要 18 分钟。
package com.mylearn.algorithm.sort; import org.apache.commons.lang.xwork.StringUtils; /** * Created by IntelliJ IDEA. * User: yingkuohao * Date: 13-9-11 * Time: 上午9:52 * CopyRight:360buy * Descrption: * 堆排序,堆是一颗完全二叉树:若设二叉树的深度为h,除第h层外,其他各层的节点都达到最大数,第h层的所有节点都集中在左边,这就是 * 完全二叉树。 二叉树中,叶子节点比非叶子节点个数多1 ,所以可以用 (n-1)/2 得到非叶子节点 * <p/> * <p/> * To change this template use File | Settings | File Templates. */ public class HeapSort { public static void main(String args[]) { Integer[] integers = new Integer[]{12, 15, 9, 24, 6, 31, 10}; HeapSort heapSort = new HeapSort(); System.out.println("初始:" + StringUtils.join(integers, ",")); // heapSort.creatHeap(integers); // heapSort.creatHeap2(integers); /* System.out.println("结果:" + StringUtils.join(integers, ",")); integers = heapSort.insert(integers, integers.length, 2);*/ heapSort.delete(integers); System.out.println("结果:" + StringUtils.join(integers, ",")); Integer[] bigData = new Integer[]{1,2,3,4,5,6,7,8,9,10,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 ,19 ,20 ,21 ,22 ,23 ,24 ,25 , 26 ,27 ,28 ,29 ,30 ,31 ,32 ,33 ,34 ,35 ,36 ,37 ,38 ,39 ,40 ,41 ,42 ,43 ,44 ,45 ,46 ,47 ,48 ,49 ,50 ,51 ,52 , 53 ,54 ,55 ,56 ,57 ,58 ,59 ,60 ,61 ,62 ,63 ,64 ,65 ,66 ,67 ,68 ,69 ,70 ,71 ,72 ,73 ,74 ,75 ,76 ,77 ,78 ,79 , 80 ,81 ,82 ,83 ,84 ,85 ,86 ,87 ,88 ,89 ,90 ,91 ,92 ,93 ,94 ,95 ,96 ,97 ,98 ,99 ,100,101,102,103,104,105,106,107,108, }; Integer[] result = heapSort.testBigData(bigData,10); System.out.println("结果:" + StringUtils.join(result, ",")); } private void execute(Integer[] integers) { //To change body of created methods use File | Settings | File Templates. } /** * 比较详细的步骤演绎 * * @param integers */ public void creatHeap(Integer[] integers) { int n = integers.length; for (int i = (n - 1) / 2; i >= 0; i--) { //叶子节点只有一个值,不需要调整位置,从非叶子节点倒序遍历,(n-1)/2 得到最后一个非叶子节点 int target = integers[i]; int left = 2 * i + 1;//左孩子 int right = 2 * i + 2; //右孩子 while (left < n) { if (right < n) { //有左右孩子,比较左右孩子,找到最小的,拿到下标 int j = left; if (integers[right] < integers[left]) { j = right; } //拿最小的孩子节点和父节点比较,如果孩子节点比父节点小,则交换 if (integers[j] < target) { int parent = (left - 1) / 2; //由于i没变,所以向下调整节点时要重新定位父节点 integers[parent] = integers[j]; integers[j] = target; left = 2 * j + 1; //向下移动孩子节点 right = 2 * j + 2; } else { break; } } else { //没有右孩子,只有左孩子,比较父节点和左孩子节点 if (integers[left] < target) { integers[i] = integers[left]; integers[left] = target; } break; } } } } /** * 简洁版本 * * @param integers */ public void creatHeap2(Integer[] integers) { int n = integers.length - 1; //数组下标从0开始,所以这里取n为最大的编码 for (int i = (n - 1) / 2; i >= 0; i--) { //叶子节点只有一个值,不需要调整位置,从非叶子节点倒序遍历,由于堆是完全二叉树,h-1层节点必须全满,所以用(n-1)/2 得到最后一个非叶子节点 genereate(integers, i, n); } } private void genereate(Integer[] integers, int parent, int n) { int target = integers[parent]; //父节点只要到叶子节点就停止循环,因为已经到底了 while (parent <= (n - 1) / 2) { int left = 2 * parent + 1; //向下移动孩子节点 int right = 2 * parent + 2; //有左右孩子,比较左右孩子,找到最小的,拿到下标 int j = left; if (right < n && integers[right] < integers[left]) { j = right; } //拿最小的孩子节点和父节点比较,如果孩子节点比父节点小,则交换 if (integers[j] < target) { integers[parent] = integers[j]; integers[j] = target; parent = j; //由于i没变,所以向下调整节点时要重新定位父节点 } else { break; } } } /** * 插入小根堆 ,插入的时候都往后顺序插入,然后调整位置。由于小根堆是按顺序拍好的,所以插入的这个位置,从根节点到插入位置 * 的父节点肯定是有序的,进行这个路径上的调整即可。 * * @param integers 目标数组 * @param i 插入位置 * @param value 插入值 * @return */ public Integer[] insert(Integer[] integers, int i, Integer value) { Integer[] tmp = integers; if (i >= integers.length) { tmp = new Integer[integers.length * 2]; System.arraycopy(integers, 0, tmp, 0, integers.length); } tmp[i] = value; insertMinHeap(tmp, i); return tmp; } /** * 插入小根堆 * * @param integers 堆数组 * @param i 插入的位置 */ private void insertMinHeap(Integer[] integers, int i) { Integer temp = integers[i]; int parent = (i - 1) / 2; while (parent >= 0 && i > 0) { //如果父节点比新加的节点小,不管 if (integers[parent] <= temp) { break; } else { //如果父节点比新加的节点大,需要调整节点,之后当前节点和父节点的指针分别上移。进行下一轮计算,看调整后有新的父节点是不是还是比目标节点小 integers[i] = integers[parent]; integers[parent] = temp; i = parent; parent = (i - 1) / 2; } } } /** * 删除小根堆 * 删除的逻辑是每次删除删根节点,然后最后一个节点的值放到根节点的位置,然后重置堆。 * * @param integers */ public void delete(Integer[] integers) { //交换首尾节点 integers[0] = integers[integers.length - 1]; integers[integers.length - 1] = null; deleteMinHeap(integers); //重置小根堆 } /** * 重置小根堆 * * @param integers */ private void deleteMinHeap(Integer[] integers) { Integer root = integers[0]; int parent = 0; int left = 1; int right = 2; while (left < integers.length - 1) { //找到左右孩子最小的值 int min = left; //由于我们删除的时候把最后一个数据置为空了,所以这里要判断一下,遍历到倒数第二层时,可能右孩子为空 if (integers[right] != null && integers[left] > integers[right]) { min = right; } //比较父节点和孩子节点,看看是否比孩子节点的最小值小。 if (root < integers[min]) { break; } else { //如果没有孩子节点小,交换值,重置parent,left,right指针 integers[parent] = integers[min]; integers[min] = root; parent = min; left = min * 2 + 1; right = min * 2 + 2; } } } /** * 海量数据查询top n最大, * 1. 先构造一个n的小根堆, * 2. 然后遍历数据,如果比根节点大,则交换,重置堆 * 3. 循环3,直至最后,得出的小根堆中的数据没有比他们大的了,这个小根堆就是top n,最大。 * * 注意:求top n最大需要构造小根堆 * top n最小需要构造大根堆 * @param bigData * @param top * @return */ public Integer[] testBigData(Integer[] bigData, int top) { //1.构建小根堆 Integer[] minHeap = new Integer[top]; System.arraycopy(bigData, 0, minHeap, 0, top); this.creatHeap(minHeap); //2.比较,重排 Integer root = minHeap[0]; for (int i = top; i < bigData.length; i++) { Integer curData = bigData[i]; if (curData > root) { minHeap[0] = curData; creatHeap(minHeap); } } return minHeap; } } |
转载地址:http://bzrrb.baihongyu.com/