堆

一种树状的数据结构

大根堆

根节点是所有节点中数值最大的节点
父节点的值总比子节点大
基本操作

Insert 向堆中插入一个值
Update 更新
Heapify 堆化
RemoveTop 删除堆顶元素
GetTop 获得堆顶元素


辅助操作

获得父节点
获得左孩子
获得右孩子
获得当前容量
判断一个节点是否是叶子节点
交换2个节点的位置



数组大根堆

用数组实现的大根堆
作用

堆排序
求最大值
求第n大的值


基本操作

Insert 向堆中插入一个值
Update 从指定的节点开始把较大的值和父节点交换直到处理到根节点
Heapify 从指定的节点开始把较小的节点和子节点中较大的那个交换直到处理到叶子节点
RemoveTop 删除堆顶元素

把堆尾部的元素换到堆顶，堆大小-1
从堆顶开始执行堆化


GetTop 获得堆顶元素


辅助操作

获得父节点

父节点和子节点的关系

leftChildIndex = parentIndex * 2 + 1
rightChildIndex = parentIndex * 2 + 2
parentIndex = (childIndex - 1) / 2




获得左孩子
获得右孩子
获得当前容量
判断一个节点是否是叶子节点

如果一个节点的孩子index超过当前容量说明这个节点没有子节点，故为叶子节点


交换2个节点的位置
获得最大容量
根据index判断一个节点是否在堆中


实现代码

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructure
{

  public class ArrayMaxHeap
  {
    int[] array;
    int size;
    int maxSize;

    public void Build(int maxSize)
    {
      array = new int[maxSize];
      this.maxSize = maxSize;
      size = 0;
    }

    public int GetSize()
    {
      return size;
    }

    public int GetMaxSize()
    {
      return maxSize;
    }

    //尾部追加再更新
    public void Insert(int value)
    {
      if (size == maxSize)
      {
        throw new Exception("size must <= max size");
      }
      array[size] = value;
      size++;
      Update(size - 1);
    }

    //把大的值往堆顶放
    //把一个大的值从下面换到父节点，直到堆顶
    void Update(int index)
    {
      if (index == 0) return;
      if (index < 0) throw new ArgumentException("index must >= 0");
      if (array[index] > array[ParentIndex(index)])
      {
        Swape(index, ParentIndex(index));
        Update(ParentIndex(index));
      }
    }

    public int LeftChildIndex(int index)
    {
      return index * 2 + 1;
    }

    public int RightChildIndex(int index)
    {
      return index * 2 + 2;
    }

    public int ParentIndex(int index)
    {
      return (index - 1) / 2;
    }

    public bool IsLeaf(int index)
    {
      return !IsInHeap(LeftChildIndex(index));
    }

    public bool IsInHeap(int index)
    {
      return 0 <= index && index < size;
    }

    private void Swape(int index1, int index2)
    {
      var temp = array[index1];
      array[index1] = array[index2];
      array[index2] = temp;
    }

    public int GetTop()
    {
      return array[0];
    }

    void Heapify(int index)
    {
      if (IsLeaf(index))
      {
        return;
      }
      //找到左边和右边最大的那个子节点，如果子节点更大，交换，对子节点执行堆化，把小的值往堆底放
      //左子节点更大
      if (array[LeftChildIndex(index)] > array[RightChildIndex(index)])
      {
        if (array[index] < array[LeftChildIndex(index)])
        {
          Swape(index, LeftChildIndex(index));
          Heapify(LeftChildIndex(index));
        }
      }
      //右孩子更大，比较右孩子
      else if (array[index] < array[RightChildIndex(index)])
      {
        Swape(index, RightChildIndex(index));
        Heapify(RightChildIndex(index));
      }

    }

    //取出堆顶，把尾部放到堆顶，执行堆化
    public int RemoveTop()
    {
      if (size == 0) throw new Exception("no element in heap");
      var top = array[0];
      array[0] = array[size - 1];
      size--;
      Heapify(0);
      return top;
    }

    public static void Test()
        {
            var array = new int[] { 2, 4, 6, 7, 8, 3, 2, 5 };
            var solution = new ArrayMaxHeap();
            solution.Build(array.Length);
            foreach (var num in array)
            {
                solution.Insert(num);
                BaseSolution.print(solution.GetTop());
                BaseSolution.print(',');
            }
            BaseSolution.println();
            while (solution.GetSize() > 0)
            {
                BaseSolution.print(solution.RemoveTop());
                BaseSolution.print(',');
            }
        }

  }

}

shift up

插入一个元素时，把元素追加到列表的最后，也就是堆的叶子节点上。然后执行shifup操作，对新元素进行从下往上的调整。
判断当前元素是否比父节点更大，如果是，则交换。否则就终止。
因为插入一个元素时，列表已经是一个大根堆，所以当出现父元素大于自己时，就没有必要继续，因为父元素的父元素值更大。

shift down


删除一个元素时，把该元素和列表的最后一个元素交换。然后列表的长度减一(如果用count计数的话)。剩余的元素进行shiftdown操作。


shiftdown，如果两个孩子中存在比自己更大的元素，就和那个孩子交换值。然后这个孩子作为根，继续这个操作。


如下: 插入时执行shiftUp，删除时执行shiftDown


// 堆排序
class Heap{
        private List<Integer> data;

        public Heap(){
            this.data = new ArrayList<>();
        }

        public void insert(int value){
            this.data.add(value);
            this.shiftUp(this.data.size() - 1);
        }
        public int pop(){
            this.swap(0, this.data.size() - 1);
            int res = this.data.remove(this.data.size() - 1);
            this.shiftDown(0);
            return res;
        }

        /**
         * 上移，元素加入时执行
         * @param k
         */
        public void shiftUp(int k){
            // 0 元素没有父元素
            // 当出现k比父元素小的时候，就没有必要继续下去，因为，父元素的父元素一定是更大的数
            while(k >= 1 && data.get(k) > data.get((k - 1) / 2)){
                swap(k, (k - 1) / 2);
                k = (k - 1) / 2;
            }
        }

        /**
         * 下移，调整堆时执行
         * @param k
         */
        public void shiftDown(int k){
            // 省略了对左孩子的判断
            while(2 * k + 1 < data.size()){
                int child =  2 * k + 1;
                if(child + 1 < this.data.size() && this.data.get(child) < this.data.get(child + 1)){
                    child += 1;
                }
                if(this.data.get(child) > this.data.get(k)){
                    this.swap(k, child);
                }
                k = child;
            }

        }

        public void swap(int left, int right){
            int temp = this.data.get(left);
            this.data.set(left, this.data.get(right));
            this.data.set(right, temp);
        }
    }
    
    // main
        _215_数组中的第k个最大元素.Heap2 heap = handle.new Heap2();
        // 建立堆
        for(int item : list){
            heap.insert(item);
        }
        for(int item : list){
            System.out.print(heap.pop() + " ");
        }

heapify

不需要一个一个的插入元素，可以直接对原数组的所有非叶节点进行heapify，即可构成一个大根堆。
((size - 1) - 1) / 2 表示最大下标减一。当然，用size/2也行，多出的几个元素都是叶子节点，都可以当成是只有一个元素的堆。

        public Heap2(List<Integer> list){
            this.data = new ArrayList<>(list);
            heapify();
        }
        public void heapify(){
            for(int i = (data.size() - 1 - 1) / 2; i >= 0; --i){
                shiftDown(i);
            }
        }

就地排序

这里的nums数组的数据从0开始拍，这样的话，按照如下方式计算父子节点

左孩子: index * 2 + 1
右孩子: index * 2 + 2
父节点: (index - 1) / 2 或者 (length -1 -1)/2。有的算法直接用 (length / 2)也不会有错，因为最右边的叶子节点都可以看成是单个的大根堆。



class Heap {
        public void heapSort(int [] nums){
            // 从第一个非叶节点开始，执行shiftdown操作
            int size = nums.length;

            // 建立一个堆
            // 很多携程(size-1)/2 或者 size/2都行
            for( int i = (size -1 - 1)/2; i >= 0; --i){
                shiftDown(nums, i, size);
            }
            // 从堆中取元素
            for (int i = size - 1; i > 0; i --){
                swap(nums, 0, i);           // i 元素被放到0位置
                shiftDown(nums, 0, i);      // 重新堆0位置的元素shiftdown
            }
        }

        /**
         * 对第i个元素执行下移操作。大根堆
         * @param nums
         * @param i
         */
        public void shiftDown(int [] nums, int k, int size){
            // 用while 少了一次循环，避免了递归
            while( 2 * k + 1 < size){
                int child = 2 * k + 1;      // 左孩子
                if ( child + 1 < size && nums[child+1] > nums[child])
                    child += 1;             // 右孩子

                if (nums[k] < nums[child]){
                    swap(nums, child, k);
                }

                k = child;                  // 从被交换的孩子开始，继续往下迭代。直到到达叶子节点
            }
        }

        public void swap(int[] a, int i, int j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }

创建大根堆
   static void buildBigHeap(int[] array, int last) {
        //从最大的非叶子节点开始（last - 1 /2）,到根节点终止
        for (int i = (last -1) / 2; i >= 0; i--) {
            int k = i;
            //判断是否超过数组界限，第一轮比较完，该子节点作为父节点时是否为最大值情况
            while ((2 * k) + 1 <= last){
                //记录最大值的下标
                int bigIndex = 2*k+1;
                //判断是否右子节点，如果相等无右子节点。小于则右
                if(bigIndex < last){
                    //判断左右子节点的大小
                    if(array[bigIndex] < array[bigIndex + 1]){
                        bigIndex++;
                    }
                }
                //最大子节点和父节点比较
                if(array[k] < array[bigIndex]){
                    MyUtil.swap(array,k,bigIndex);
                    System.out.println(Arrays.toString(array)+"有交换"+ "\t" +"父节点 = " + k +  "\t" + "最大子节点 = " + bigIndex);
                    k = bigIndex;
                }
                else {
                    System.out.println(Arrays.toString(array)+"无交换");
                    break;
                }
            }
        }
    }

创建大根堆思路
首先找到最后的父节点 ，从下标0开始所以为int last = (array.length -1 -1 )/2

所以父节点一共有0 到 last 个

记录一下当前父节点的下标

以左子节点来判断是否超过数组界限

找出左右子节点的最大值

然后和父节点的值进行比较 交换位置
大根堆排序code
public static void  headSort(int[] nums){
    System.out.println("原始数组 =" + Arrays.toString(nums));
    System.out.println("-----------------------------------");
    for(int i = nums.length - 1 ; i > 0; i--){
        buildBigHeap(nums, i);
        MyUtil.swap(nums, i , 0);
    }
}

思路
每次都将前面的值放到最后

因为每次放完后在进行大根堆重组的时候，重组数组大小减1，所以 9 8 7 6 5 4 3 2 1 的顺序排成从小到大
测试code
public static void main(String[] args){
    int[] array = MyUtil.createArray();
    int[] arrays = new int[array.length];
    System.arraycopy(array,0,arrays,0,array.length);
    //系统排序
    Arrays.sort(arrays);
    //堆排序
    HeapSort.headSort(array);
    boolean compare = MyUtil.compare(array,arrays);
    System.out.println(compare);
}

问题描述：

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

样例

输入：1, 2, 3, 4
输出：1,1.5,2,2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

使用大根堆维护序列的前半部分，使用小根堆维护序列的后半部分。序列是指的从小到大排列。首先向大根堆里面加入元素，如果加入元素不满足条件，那么再进行下一步操作，其中条件是：1）大根堆里面的元素最多只能比小根堆的元素多1个，如果多两个的话，就需要将大根堆的元素弹出来放到小根堆里面去，2）如果大根堆里面的堆顶元素大于小根堆里面的堆顶元素，那么这样的序列不是有序的，则需要交换这两个元素使得大的部分在小根堆里，小的部分在大根堆里。
class Solution {
public:
    priority_queue<int> max_heap;
    priority_queue<int,vector<int>,greater<int>> min_heap;
    void insert(int num){
        max_heap.push(num);
        if(min_heap.size()&&max_heap.top()>min_heap.top())
        {
            auto maxv=max_heap.top(),minv=min_heap.top();
            max_heap.pop(),min_heap.pop();
            max_heap.push(minv),min_heap.push(maxv);
        }
        if(max_heap.size()>min_heap.size()+1)
        {
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }

    double getMedian(){
        if(max_heap.size() + min_heap.size() & 1) return max_heap.top();
        return (max_heap.top()+min_heap.top())/2.0;
    }
};