1.概念

堆排序，为了平衡入队和出队
image.png

2. 堆排序基本存储

2.1 二叉堆

2.1.1 概念

必须是完全二叉树，堆中某个节点的值总是不大于其父节点的值，并要求左节点大于右节点
image.png

2.1.2 堆类基本代码实现

  1. package test2;
  3. import java.util.*;
  4. public class MaxHeap {
  5.     private int[] Item;
  6.     //数组中已有的元素
  7.     private int count;
  8.     public int getCount() {
  9.         return count;
  10.     }
  11.     public void setCount(int count) {
  12.         this.count = count;
  13.     }
  14.     //初始化数组
  15.     public MaxHeap(int capacity) {
  16.         Item = new int[capacity+1];
  17.         count = 0;
  18.     }
  19.     //随机添加一个数组，并让这个数组成为最大堆
  20.     public MaxHeap(int[] arr) {
  21.         //初始化数组
  22.         Item = new int[arr.length+1];
  23.         count = 0;
  24.         //将这个数组插入进去
  25.         for(int i = 0; i<arr.length;i++) {
  26.             Item[i+1] = arr[i];
  27.             count++;
  28.         }
  29.         //对这个数组进行堆排序
  30.         for(int i = count/2 ; i>=1 ;i--) {
  31.             shiftDown(i);
  32.         }
  33.     }
  35.     //循环遍历数组
  36.     public void printfArray() {
  37.         System.out.println("数组中的元素个数:"+count);
  38.         System.out.print("数组:");
  39.         int i = 0;
  40.         do {
  41.             System.out.print(Item[i]+" ");
  42.             i++;
  43.         }while(i<count+1 && Item[i]!=0);
  44.         System.out.println();
  45.     }
  47.     //在堆中添加元素
  48.     public void insert(int item) {
  49.         Item[count + 1] = item;
  50.         count++;
  51.         shiftUP(count);
  52.     }
  54.     //将k索引的值移到他应该在的位置 
  55.     private void shiftUP(int k) {
  56.         //如果他大于他的父节点则交换位置,一直查询到根节点
  57.         while(Item[k]> Item[k/2] && k>1 ) {
  58.             swapArr(Item, k, k/2);
  59.             k/=2;
  60.         }
  61.     } 
  62.     //移除根节点
  63.     public void request() {
  65.     }
  66.     //只能移除根节点，值移除后,依然保持数组的性质
  67.     private void shiftDown(int k) {
  68.         while(2*k<=count) {
  69.             int j = 2*k;
  70.             //如果有右孩子 并且大于左孩子
  71.             if(j + 1 <=count &&Item[j+1]>Item[j]) {
  72.                 j++;
  73.             }
  74.             //如果max(左孩子，右孩子)小于父亲
  75.             if(Item[j]<Item[k]) {
  76.                 break;
  77.             }
  78.             swapArr(Item, k, j);
  79.             k = j;
  80.         }
  81.     }
  82.     //返回根节点的值
  83.     public int extractMax() {
  84.         int v = 0;
  85.         if(count>0) {
  86.             v = Item[1];
  87.             //将最后一个元素移到第一个
  88.             swapArr(Item, 1, count);
  89.             count--;
  90.             shiftDown(1);
  91.         }
  92.         return v;
  93.     }
  94.     //数组中元素交换
  95.     private void swapArr(int[] arr,int index1,int index2) {
  96.         int i = arr[index2];
  97.         arr[index2] = arr[index1];
  98.         arr[index1] = i;         
  99.     }
  100. }

3. 堆排序

3.1 运行

对维护动态数据有更好的效果

package test2;

import java.util.Random;

public class MaxHeapTest {
    public static void main(String[] args) {
        int[] arr = Test.genereateRandomArray(20000, 15,20);
        //int arr[]  = {1,2,3,4,5,6,7,8,9};

        long startTime1=System.currentTimeMillis();   //获取开始时间
        heap(arr);
        long endTime1=System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间： "+(endTime1-startTime1)+"ms");
        Test.printfArray(arr);

    }

    //堆排序
    public static void heap(int[] arr) {
        MaxHeap max = new MaxHeap(arr);
        for(int i = max.getCount();i>0;i--) {
            // extractMax() 获取最大元素并删除
            arr[i-1] = max.extractMax();
        }
    }
}

image.png

3.2 原地堆排序

    //原地堆排序
    public  void heapSort() {
        /*
         * 将第一个元素和最后元素交换
         * 交换后对第一个元素进行shiftDown操作，维护最大堆性质
         * 对堆进行操作的长度--
         * 操作完成后 Item由最大堆变成了一个顺序数组
         */
        for(int i =n-1;i>0;i--) {
            swapArr(Item, i, 0);
            __shiftDown(0,i);
        }
    }

    //下标从 0 开始的shiftDown操作
    private  void __shiftDown(int i,int len){
        //如果该下标有左孩子
        while(i*2+1<len) {
            //System.out.println("a");
            int j = i*2+1;
            //如果存在右孩子，并且大于左孩子
            if(i*2+2<len && Item[i*2+2]>Item[i*2+1]) {
                j++;
            }
            //如果都小于父亲 则结束函数
            if(Item[i]>Item[j]) {
                break;
            }
            swapArr(Item,j, i);
            i = j;
        }
    }

4.索引堆

保证原数组不变，将索引进行排序

核心代码 无检测索引溢出等情况

//索引最大堆
public class IndexMaxHeap {
    //需要一个新的数组存储索引
    private int[] Indexes;
    private int[] Item;
    //Item值下标在 indexes中存储中的下标
    private int[] Reverse;
    //数组长度
    private int count;

    public IndexMaxHeap() {
        this(10);
    }

    //构造函数 创建一个capacity长度的数组(算0 index)
    public IndexMaxHeap(int capacity) {
        //初始化数组 和索引数组
        Item  = new int[capacity];
        Indexes = new int[capacity];
        Reverse = new int[capacity];
        count = capacity;
    }

    /*
     * 构造函数
     *  传入数组 
     */
    public IndexMaxHeap(int[] arr) {
        // 初始化原数组和索引数组
        Item  = new int[arr.length+10];
        Indexes = new int[arr.length+10];
        Reverse = new int[arr.length+10];
        count = arr.length;
        for(int i = 0;i<count;i++) {
            Item[i] = arr[i];
            Indexes[i] = i;        
            Reverse[i] = i;
        }
        //for(int j = 0;j<count;j++) {
        //    Reverse[Indexes[j]] = j;
        //}
        //将Item进行最大堆排序
        for(int i = (count-2)/2; i>=0;i--) {
            shiftDown(i);            
        }
    }

    //ShiftDown操作 将根接点放在他应该在的位置
    public void shiftDown(int i){
         /* 循环结束条件
          * 则循环到接点无左孩子 
          * 该孩子接点为i左孩子的index（2i+1）小于count则循环继续 则 i = j
          * 左孩子的index大于或者等于count循环结束
         */
        while(2*i+1 < count) {
            //j 代表 max(左孩子，右孩子) 的下标
            int j = 2*i+1;
            //如果右孩子存在 并且右孩子的值大于左孩子
            if(j+1<count && Item[Indexes[j+1]]>Item[Indexes[j]]) {
                j = j+1;
            }
            //如果该值大于j的值 则函数结束
            if(Item[Indexes[i]]>Item[Indexes[j]]) {
                return;
            }
            //将ij交换位置
            Test.swapArr(Indexes, i, j);
            Reverse[Indexes[i]] = i;
            Reverse[Indexes[j]] = j;
            i = j;
        }
    }
    //插入操作
    public void insert(int value) {
        Item[count] = value;
        Indexes[count] = count;
        Reverse[count] = count;
        count++;    
        shiftUp(count-1);
    }

    //向上移动
    public void shiftUp(int index) {
        /*
         * 循环结束条件
         * 该index 无父节点则代表结束
         * 则 （index-1）/2 < 0 则代表结束 
         */
        while(index>0) {
            int j = (index-1)/2;
            if(Item[Indexes[index]] < Item[Indexes[j]]) {
                return;
            }
            Test.swapArr(Indexes, index, j);
            Reverse[Indexes[index]] = index;
            Reverse[Indexes[j]] = j;
            index = j;
        }
    }
    // 将索引i的值改变为新值 并保证堆的性质不变
    public void change(int index, int value) {
        Item[index] = value;

        //找到index下标的值
//        for(int i = 0; i<count;i++) {
//            if(Indexes[i] == index) {
//                //先保证他本身为一个最大堆
//                shiftUp(i);
//                //然后将他放在合适的位置
//                shiftDown(i);
//                return;
//            }
//        } 
        int j = Reverse[index];
        shiftUp(j);
        shiftDown(j);
    }

    //循环遍历数组
    public void printfArray() {
        System.out.println("数组中的元素个数:"+count);
        System.out.print("Item:");
        int i = 0;
        do {
            System.out.print(Item[i]+" ");
            i++;
        }while(i<count);
        System.out.println();
        System.out.print("Indexes:");
        int j = 0;
        do {
            System.out.print(Indexes[j]+" ");
            j++;
        }while(j<count );
        System.out.println();
        System.out.print("Reverse:");
        int z = 0;
        do {
            System.out.print(Reverse[z]+" ");
            z++;
        }while(z<count );
        System.out.println();
    }
}

image.png