devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构 -- 堆

作者：笔触狂放9 | 2024-04-08 18:03:34

赞

踩

数据结构 -- 堆

大顶堆定义:父节点要比任意两个孩子的值要大

heapify()建堆之后:

过程:威廉姆斯建堆算法  n*log(n)

这个时间复杂度如何估算呢?

得到这样一个式子以后我们就可以开始算时间复杂度了,但是这似乎有点为难数学不好的同学,但是没有关系!我们可以用这个网站 

Wolfram|Alpha：计算型智能 (wolframalpha.com)

输入:

Sum[\(40)Divide[Power[2,x],Power[2,i]]*\(40)i-1\(41)\(41),{i,1,x}]

高度为4  ==>2^4 - 4 -1 = 11 意思是交换11次就能建堆

算法实现:

这个建堆操作要非常熟练!

  1. import java.util.Arrays;
  2.  
  3. /**
  4.  * 大顶堆
  5.  */
  6. public class MaxHeap {
  7.     int[] array;
  8.     int size;
  9.  
  10.     public MaxHeap(int[] array){
  11.         this.array = array;
  12.         this.size = array.length;
  13.         heapify();
  14.     }
  15.  
  16.     public MaxHeap(int capacity){
  17.         this.array = new int[capacity];
  18.     }
  19.  
  20.     //建堆
  21.     private void heapify(){
  22.         //如何找到最后这个非叶子节点 这个有公式:size>>1-1  or (size/2-1)
  23.         for(int i = size/2-1;i>=0;i--){
  24.             down(i);
  25.         }
  26.     }
  27.     /**
  28.      * 删除堆顶元素
  29.      * @Returns:堆顶元素
  30.      */
  31.     public int poll(){
  32.         return 0;
  33.     }
  34.  
  35.  
  36.     //将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
  37.     private void down(int parent){
  38.          int left = parent*2+1;
  39.          int right = left+1;
  40.          int max = parent;
  41.          if(left<size && array[left]>array[max]){
  42.              max = left;
  43.          }
  44.         if(right<size && array[right]>array[max]){
  45.             max = right;
  46.         }
  47.         if(max!=parent){//找到更大的孩子
  48.             swap(max,parent);
  49.             down(max);
  50.         }
  51.     }
  52.  
  53.     //交换两个索引处的元素
  54.     private void swap(int i,int j){
  55.         int t = array[i];
  56.         array[i] = array[j];
  57.         array[j] = t;
  58.     }
  59.  
  60.     public static void main(String[] args) {
  61.         int[] array = {1,2,3,4,5,6,7};
  62.         MaxHeap maxHeap = new MaxHeap(array);
  63.         System.out.println(Arrays.toString(maxHeap.array));
  64.         //[7, 5, 6, 4, 2, 1, 3]
  65.     }
  66.  
  67. }

填充剩余代码:

  1.     /**
  2.      * 删除堆顶元素
  3.      * @Returns:堆顶元素
  4.      */
  5.     public int poll(){
  6.         int top = array[0];
  7.         swap(0,size-1);
  8.         size--;
  9.         down(0);
  10.         return top;
  11.     }

  1. /**
  2.      * 替换堆顶元素
  3.      * @param replaced - 新元素
  4.      */
  5.     public void replace(int replaced){
  6.         array[0] = replaced;
  7.         down(0);
  8.     }

  1. import java.util.Arrays;
  2.  
  3. /**
  4.  * 大顶堆
  5.  */
  6. public class MaxHeap {
  7.     int[] array;
  8.     int size;
  9.  
  10.     public MaxHeap(int[] array){
  11.         this.array = array;
  12.         this.size = array.length;
  13.         heapify();
  14.     }
  15.  
  16.     public MaxHeap(int capacity){
  17.         this.array = new int[capacity];
  18.     }
  19.  
  20.     //建堆
  21.     private void heapify(){
  22.         //如何找到最后这个非叶子节点 这个有公式:size>>1-1  or (size/2-1)
  23.         for(int i = size/2-1;i>=0;i--){
  24.             down(i);
  25.         }
  26.     }
  27.  
  28.     /**
  29.      * 删除堆顶元素
  30.      * @return:堆顶元素
  31.      */
  32.     public int peek(){
  33.         //当然如果这个堆里面没有数据的话 会报错
  34.         //这个可以抛异常
  35.         return array[0];
  36.     }
  37.     /**
  38.      * 删除堆顶元素
  39.      * @Returns:堆顶元素
  40.      */
  41.     public int poll(){
  42.         int top = array[0];
  43.         swap(0,size-1);
  44.         size--;
  45.         down(0);
  46.         return top;
  47.     }
  48.  
  49.     /**
  50.      * 删除指定索引处元素
  51.      * @param:index - 索引
  52.      * @return:被删除元素
  53.      */
  54.     public int poll(int index){
  55.         //可以一下考虑 堆为空的时候,这里就先不写了
  56.         int deleted = array[index];
  57.         swap(index,size-1);
  58.         size--;
  59.         down(index);
  60.         return deleted;
  61.     }
  62.  
  63.     /**
  64.      * 替换堆顶元素
  65.      * @param replaced - 新元素
  66.      */
  67.     public void replace(int replaced){
  68.         array[0] = replaced;
  69.         down(0);
  70.     }
  71.  
  72.     /**
  73.      * 堆的尾部添加元素
  74.      * @param:offered-新元素
  75.      * @return:是否添加成功
  76.      */
  77.     public boolean offer(int offered){
  78.         if(size==array.length){
  79.             return false;
  80.         }
  81.         up(offered);
  82.         size++;
  83.         return true;
  84.     }
  85.  
  86.     //将 offered元素上浮:直到offered小于父元素或到堆顶
  87.     private void up(int offered){
  88.         int child = size;
  89.         while(child>0){
  90.             int parent = (child-1)/2;
  91.             if(offered>array[parent]){
  92.                 array[child] = array[parent];
  93.                 
  94.             }else{
  95.                 break;
  96.                 
  97.             }
  98.             child = parent;
  99.         }
  100.         array[child]=offered;
  101.     }
  102.  
  103.  
  104.     //将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
  105.     private void down(int parent){
  106.          int left = parent*2+1;
  107.          int right = left+1;
  108.          int max = parent;
  109.          if(left<size && array[left]>array[max]){
  110.              max = left;
  111.          }
  112.         if(right<size && array[right]>array[max]){
  113.             max = right;
  114.         }
  115.         if(max!=parent){//找到更大的孩子
  116.             swap(max,parent);
  117.             down(max);
  118.         }
  119.     }
  120.  
  121.     //交换两个索引处的元素
  122.     private void swap(int i,int j){
  123.         int t = array[i];
  124.         array[i] = array[j];
  125.         array[j] = t;
  126.     }
  127.  
  128.     public static void main(String[] args) {
  129.         int[] array = {1,2,3,4,5,6,7};
  130.         MaxHeap maxHeap = new MaxHeap(array);
  131.         System.out.println(Arrays.toString(maxHeap.array));
  132.         //[7, 5, 6, 4, 2, 1, 3]
  133.     }
  134.  
  135. }

堆排序

1.heapify 建立大顶堆

2.将堆顶与堆底交换(最大元素被交换到堆底),缩小并下潜调整堆

3.重复第二步直至堆里剩一个元素

  1. public class MaxHeap {
  2.     int[] array;
  3.     int size;
  4.  
  5.     public MaxHeap(int[] array){
  6.         this.array = array;
  7.         this.size = array.length;
  8.         heapify();
  9.     }
  10.  
  11.     public MaxHeap(int capacity){
  12.         this.array = new int[capacity];
  13.     }
  14.  
  15.     //建堆
  16.     private void heapify(){
  17.         //如何找到最后这个非叶子节点 这个有公式:size>>1-1  or (size/2-1)
  18.         for(int i = size/2-1;i>=0;i--){
  19.             down(i);
  20.         }
  21.     }
  22.  
  23.     /**
  24.      * 删除堆顶元素
  25.      * @return:堆顶元素
  26.      */
  27.     public int peek(){
  28.         //当然如果这个堆里面没有数据的话 会报错
  29.         //这个可以抛异常
  30.         return array[0];
  31.     }
  32.     /**
  33.      * 删除堆顶元素
  34.      * @Returns:堆顶元素
  35.      */
  36.     public int poll(){
  37.         int top = array[0];
  38.         swap(0,size-1);
  39.         size--;
  40.         down(0);
  41.         return top;
  42.     }
  43.  
  44.     /**
  45.      * 删除指定索引处元素
  46.      * @param:index - 索引
  47.      * @return:被删除元素
  48.      */
  49.     public int poll(int index){
  50.         //可以一下考虑 堆为空的时候,这里就先不写了
  51.         int deleted = array[index];
  52.         swap(index,size-1);
  53.         size--;
  54.         down(index);
  55.         return deleted;
  56.     }
  57.  
  58.     /**
  59.      * 替换堆顶元素
  60.      * @param replaced - 新元素
  61.      */
  62.     public void replace(int replaced){
  63.         array[0] = replaced;
  64.         down(0);
  65.     }
  66.  
  67.     /**
  68.      * 堆的尾部添加元素
  69.      * @param:offered-新元素
  70.      * @return:是否添加成功
  71.      */
  72.     public boolean offer(int offered){
  73.         if(size==array.length){
  74.             return false;
  75.         }
  76.         up(offered);
  77.         size++;
  78.         return true;
  79.     }
  80.  
  81.     //将 offered元素上浮:直到offered小于父元素或到堆顶
  82.     private void up(int offered){
  83.         int child = size;
  84.         while(child>0){
  85.             int parent = (child-1)/2;
  86.             if(offered>array[parent]){
  87.                 array[child] = array[parent];
  88.  
  89.             }else{
  90.                 break;
  91.  
  92.             }
  93.             child = parent;
  94.         }
  95.         array[child]=offered;
  96.     }
  97.  
  98.  
  99.     //将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
  100.     private void down(int parent){
  101.          int left = parent*2+1;
  102.          int right = left+1;
  103.          int max = parent;
  104.          if(left<size && array[left]>array[max]){
  105.              max = left;
  106.          }
  107.         if(right<size && array[right]>array[max]){
  108.             max = right;
  109.         }
  110.         if(max!=parent){//找到更大的孩子
  111.             swap(max,parent);
  112.             down(max);
  113.         }
  114.     }
  115.  
  116.     //交换两个索引处的元素
  117.     private void swap(int i,int j){
  118.         int t = array[i];
  119.         array[i] = array[j];
  120.         array[j] = t;
  121.     }
  122.  
  123.     public static void main(String[] args) {
  124.         int[] array = {2,3,1,7,6,4,5};
  125.         MaxHeap heap = new MaxHeap(array);
  126.         System.out.println(Arrays.toString(heap.array));//[7, 6, 5, 3, 2, 4, 1]
  127.         while(heap.size>1){
  128.             heap.swap(0,heap.size-1);
  129.             heap.size--;
  130.             heap.down(0);
  131.         }
  132.         System.out.println(Arrays.toString(heap.array));//
  133.         //[1, 2, 3, 4, 5, 6, 7]
  134.     }
  135.  
  136. }

215. 数组中的第K个最大元素 - 力扣（LeetCode）

先来看看思路:

这里使用小顶堆来解决这个问题,为什么不是大顶堆 咱们往后看

示例一:求第k大 我们可以先把数组前两个放进小顶堆中

实例二:求第k=4大,我们可以先把数组前四个小顶堆中(当然了大顶堆也可以 但是这里用小顶堆)

如果新加进来的元素比堆中的元素逗都小,那么我们什么也不做

如果进来的元素大就替换掉堆顶元素

例子:比如实例1中第三个元素是1 所以咱们什么也不做 接着看下一个数字5,发现5比堆顶元素2大,那么就要进行替换,然后重新调整小顶堆

经过这些运算,小顶堆中就是两个最大的元素 最终返回堆顶元素即可.

  1. public class MinHeap {
  2.     int[] array;
  3.     int size;
  4.  
  5.     public MinHeap(int[] array){
  6.         this.array = array;
  7.         this.size = array.length;
  8.         heapify();
  9.     }
  10.  
  11.     public MinHeap(int capacity){
  12.         this.array = new int[capacity];
  13.     }
  14.  
  15.     //建堆
  16.     private void heapify(){
  17.         //如何找到最后这个非叶子节点 这个有公式:size>>1-1  or (size/2-1)
  18.         for(int i = size/2-1;i>=0;i--){
  19.             down(i);
  20.         }
  21.     }
  22.  
  23.     /**
  24.      * 删除堆顶元素
  25.      * @return:堆顶元素
  26.      */
  27.     public int peek(){
  28.         //当然如果这个堆里面没有数据的话 会报错
  29.         //这个可以抛异常
  30.         return array[0];
  31.     }
  32.     /**
  33.      * 删除堆顶元素
  34.      * @Returns:堆顶元素
  35.      */
  36.     public int poll(){
  37.         int top = array[0];
  38.         swap(0,size-1);
  39.         size--;
  40.         down(0);
  41.         return top;
  42.     }
  43.  
  44.     /**
  45.      * 删除指定索引处元素
  46.      * @param:index - 索引
  47.      * @return:被删除元素
  48.      */
  49.     public int poll(int index){
  50.         //可以一下考虑 堆为空的时候,这里就先不写了
  51.         int deleted = array[index];
  52.         swap(index,size-1);
  53.         size--;
  54.         down(index);
  55.         return deleted;
  56.     }
  57.  
  58.     /**
  59.      * 替换堆顶元素
  60.      * @param replaced - 新元素
  61.      */
  62.     public void replace(int replaced){
  63.         array[0] = replaced;
  64.         down(0);
  65.     }
  66.  
  67.     /**
  68.      * 堆的尾部添加元素
  69.      * @param:offered-新元素
  70.      * @return:是否添加成功
  71.      */
  72.     public boolean offer(int offered){
  73.         if(size==array.length){
  74.             return false;
  75.         }
  76.         up(offered);
  77.         size++;
  78.         return true;
  79.     }
  80.  
  81.     //将 offered元素上浮:直到offered小于父元素或到堆顶
  82.     private void up(int offered){
  83.         int child = size;
  84.         while(child>0){
  85.             int parent = (child-1)/2;
  86.             if(offered<array[parent]){
  87.                 array[child] = array[parent];
  88.  
  89.             }else{
  90.                 break;
  91.  
  92.             }
  93.             child = parent;
  94.         }
  95.         array[child]=offered;
  96.     }
  97.  
  98.  
  99.     //将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
  100.     private void down(int parent){
  101.         int left = parent*2+1;
  102.         int right = left+1;
  103.         int min = parent;
  104.         if(left<size && array[left]<array[min]){
  105.             min = left;
  106.         }
  107.         if(right<size && array[right]<array[min]){
  108.             min = right;
  109.         }
  110.         if(min!=parent){//找到更大的孩子
  111.             swap(min,parent);
  112.             down(min);
  113.         }
  114.     }
  115.  
  116.     //交换两个索引处的元素
  117.     private void swap(int i,int j){
  118.         int t = array[i];
  119.         array[i] = array[j];
  120.         array[j] = t;
  121.     }
  122.  
  123. }
  1. /**
  2.  * 求数组中第K大的元素
  3.  * 解题思路:
  4.  * 1.向小顶堆放入前k个元素
  5.  * 2.剩余元素
  6.  *
  7.  * 若<=堆顶元素,则略过
  8.  * 若>堆顶元素,则替换堆顶元素
  9.  *
  10.  * 3.这样小顶堆始终保留的是到目前为止,第K大的元素
  11.  * 4.循环结束,堆顶元素即为第K大元素
  12.  */
  13. public class E02Leetcode215 {
  14.  
  15.     public int findthLargest(int[] numbers,int k){
  16.         MinHeap heap = new MinHeap(k);
  17.         for (int i = 0; i < k; i++) {
  18.             heap.offer(numbers[i]);
  19.         }
  20.         for (int i = k; i < numbers.length; i++) {
  21.             if(numbers[i] > heap.peek()){
  22.                 heap.replace(numbers[i]);
  23.             }
  24.         }
  25.         return heap.peek();
  26.     }
  27.     public static void main(String[] args){
  28.         //应为5
  29.         System.out.println(new E02Leetcode215().findthLargest(new int[]{3,2,1,5,6,4},2));
  30.         //应为4
  31.         System.out.println(new E02Leetcode215().findthLargest(new int[]{3,2,3,1,2,4,5,5,6},4));
  32.  
  33.  
  34.     }
  35. }

703. 数据流中的第 K 大元素 - 力扣（LeetCode）

跟上面那倒题目的区别是:上面的数据是固定的 而这题反之

在数组中用堆排序并不是最优的选择因为有更优秀的算法.但是对于这道题目,最好的选择就是使用堆了.

  1. public class MinHeap {
  2.     int[] array;
  3.     int size;
  4.  
  5.     public MinHeap(int[] array){
  6.         this.array = array;
  7.         this.size = array.length;
  8.         heapify();
  9.     }
  10.  
  11.     public MinHeap(int capacity){
  12.         this.array = new int[capacity];
  13.     }
  14.  
  15.     //建堆
  16.     private void heapify(){
  17.         //如何找到最后这个非叶子节点 这个有公式:size>>1-1  or (size/2-1)
  18.         for(int i = size/2-1;i>=0;i--){
  19.             down(i);
  20.         }
  21.     }
  22.  
  23.     /**
  24.      * 删除堆顶元素
  25.      * @return:堆顶元素
  26.      */
  27.     public int peek(){
  28.         //当然如果这个堆里面没有数据的话 会报错
  29.         //这个可以抛异常
  30.         return array[0];
  31.     }
  32.     /**
  33.      * 删除堆顶元素
  34.      * @Returns:堆顶元素
  35.      */
  36.     public int poll(){
  37.         int top = array[0];
  38.         swap(0,size-1);
  39.         size--;
  40.         down(0);
  41.         return top;
  42.     }
  43.  
  44.     /**
  45.      * 删除指定索引处元素
  46.      * @param:index - 索引
  47.      * @return:被删除元素
  48.      */
  49.     public int poll(int index){
  50.         //可以一下考虑 堆为空的时候,这里就先不写了
  51.         int deleted = array[index];
  52.         swap(index,size-1);
  53.         size--;
  54.         down(index);
  55.         return deleted;
  56.     }
  57.  
  58.     /**
  59.      * 替换堆顶元素
  60.      * @param replaced - 新元素
  61.      */
  62.     public void replace(int replaced){
  63.         array[0] = replaced;
  64.         down(0);
  65.     }
  66.  
  67.     /**
  68.      * 堆的尾部添加元素
  69.      * @param:offered-新元素
  70.      * @return:是否添加成功
  71.      */
  72.     public boolean offer(int offered){
  73.         if(size==array.length){
  74.             return false;
  75.         }
  76.         up(offered);
  77.         size++;
  78.         return true;
  79.     }
  80.  
  81.     //将 offered元素上浮:直到offered小于父元素或到堆顶
  82.     private void up(int offered){
  83.         int child = size;
  84.         while(child>0){
  85.             int parent = (child-1)/2;
  86.             if(offered<array[parent]){
  87.                 array[child] = array[parent];
  88.  
  89.             }else{
  90.                 break;
  91.  
  92.             }
  93.             child = parent;
  94.         }
  95.         array[child]=offered;
  96.     }
  97.  
  98.  
  99.     //将parent索引处的元素下潜:与两个孩子较大者交换,直到没孩子或孩子没它大
  100.     private void down(int parent){
  101.         int left = parent*2+1;
  102.         int right = left+1;
  103.         int min = parent;
  104.         if(left<size && array[left]<array[min]){
  105.             min = left;
  106.         }
  107.         if(right<size && array[right]<array[min]){
  108.             min = right;
  109.         }
  110.         if(min!=parent){//找到更大的孩子
  111.             swap(min,parent);
  112.             down(min);
  113.         }
  114.     }
  115.  
  116.     public boolean isFull(){
  117.         return size==array.length;
  118.     }
  119.  
  120.     //交换两个索引处的元素
  121.     private void swap(int i,int j){
  122.         int t = array[i];
  123.         array[i] = array[j];
  124.         array[j] = t;
  125.     }
  126.  
  127. }
  1. public class E03Leetcode703 {
  2.  
  3.     //将小顶堆MinHeap作为成员变量
  4.     private MinHeap heap;
  5.  
  6.     public E03Leetcode703(int k,int[] nums){
  7.         heap = new MinHeap(k);
  8.         for(int num:nums){
  9.             add(num);
  10.         }
  11.     }
  12.  
  13.     //此方法会被不断调用,模拟数据流中新来的元素
  14.     public int add(int val){
  15.         if(!heap.isFull()){
  16.             heap.offer(val);
  17.         }
  18.         //这样写有些测试样例过不了 因为这是一个流 有可能数组中刚刚开始凑不满三个
  19.         //所以我们可以在小顶堆实现ifFull()
  20.         else if(val>heap.peek()){
  21.             heap.replace(val);
  22.         }
  23.         return heap.peek();
  24.     }
  25.  
  26.     public static void main(String[] args){
  27.         E03Leetcode703 test = new E03Leetcode703(3,new int[]{4,5,8,2});
  28.  
  29.         //小顶堆  4 5 8
  30.         //跟上一题思路类似
  31.         //因为k = 3 所以 4 5 8添加
  32.  
  33.         System.out.println(test.add(3));//[4 5 8] ==>4
  34.         System.out.println(test.add(5));//[5,5,8] ==> 5
  35.         System.out.println(test.add(10));//[5,8,10] ==> 5
  36.         System.out.println(test.add(9));// [8 9 10] ==> 8
  37.         System.out.println(test.add(4));// [8 9 10] ==> 8
  38.     }
  39. }

295. 数据流的中位数 - 力扣（LeetCode）

可能你会想把数据排序然后就可以求中位数了,但是这是数据流,数据不断变化,这样效率很低

1   2   3   7   8   9
思路:
我们不是说非要把所有的数据收集起来然后重头到尾排个序,我们可以把所有数据分成两部分
一部分是较小的数据 大概占一半 一部分是较大的数据  从小的里面挑大的 大的里面挑小的
s   s   s  g   g   g
        3   7
    大顶堆   小顶堆   所以可以用两个堆来解决

  1. import java.util.Arrays;
  2.  
  3. /**
  4.  * <h3>数据流的中位数</h3>
  5.  */
  6. public class E04Leetcode295_1 {
  7.  
  8.     /**
  9.      * 为了保证两边数据量的平衡
  10.      * <ul>
  11.      * <li>两边个数一样时,左边个数加一</li>
  12.      * <li>两边个数不一样时,右边个数加一</li>
  13.      * </ul>
  14.      * 但是, 随便一个数能直接加入吗?
  15.      * <ul>
  16.      * <li>左边个数加一时, 把新元素加在右边，弹出右边最小的加入左边</li>
  17.      * <li>右边个数加一时, 把新元素加在左边，弹出左边最小的加入右边</li>
  18.      * </ul>
  19.      */
  20.     public void addNum(int num) {
  21.         if (left.size() == right.size()) {
  22.             right.offer(num);
  23.             left.offer(right.poll());
  24.         } else {
  25.             left.offer(num);
  26.             right.offer(left.poll());
  27.         }
  28.     }
  29.  
  30.     private Heap left = new Heap(10, true);
  31.     private Heap right = new Heap(10, false);
  32.  
  33.     @Override
  34.     public String toString() {
  35.         int size = left.size;
  36.         int[] left = new int[size];
  37.         for (int i = 0; i < left.length; i++) {
  38.             left[size - 1 - i] = this.left.array[i];
  39.         }
  40.         int[] right = Arrays.copyOf(this.right.array, this.right.size);
  41.         return Arrays.toString(left) + " <-> " + Arrays.toString(right);
  42.     }
  43.  
  44.     /**
  45.      * <ul>
  46.      *     <li>两边数据一致, 左右各取堆顶元素求平均</li>
  47.      *     <li>左边多一个, 取左边堆顶元素</li>
  48.      * </ul>
  49.      */
  50.     public double findMedian() {
  51.         if (left.size() == right.size()) {
  52.             return (left.peek() + right.peek()) / 2.0;
  53.         } else {
  54.             return left.peek();
  55.         }
  56.     }
  57.  
  58.     public static void main(String[] args) {
  59.         E04Leetcode295_1 test = new E04Leetcode295_1();
  60.         test.addNum(1);
  61.         test.addNum(2);
  62.         test.addNum(3);
  63.         test.addNum(7);
  64.         test.addNum(8);
  65.         test.addNum(9);
  66.         System.out.println(test);
  67.         System.out.println(test.findMedian());
  68.         test.addNum(10);
  69.         System.out.println(test);
  70.         System.out.println(test.findMedian());
  71.         test.addNum(4);
  72.         System.out.println(test);
  73.         System.out.println(test.findMedian());
  74.     }
  75.  
  76.  
  77. }
  1. /**
  2.  * 可以扩容的heap max用于指定是大顶堆还是小顶堆
  3.  */
  4. public class Heap {
  5.     int[] array;
  6.     int size;
  7.     boolean max;
  8.  
  9.     public int size() {
  10.         return size;
  11.     }
  12.  
  13.     public Heap(int capacity, boolean max) {
  14.         this.array = new int[capacity];
  15.         this.max = max;
  16.     }
  17.  
  18.     /**
  19.      * 获取堆顶元素
  20.      *
  21.      * @return 堆顶元素
  22.      */
  23.     public int peek() {
  24.         return array[0];
  25.     }
  26.  
  27.     /**
  28.      * 删除堆顶元素
  29.      *
  30.      * @return 堆顶元素
  31.      */
  32.     public int poll() {
  33.         int top = array[0];
  34.         swap(0, size - 1);
  35.         size--;
  36.         down(0);
  37.         return top;
  38.     }
  39.  
  40.     /**
  41.      * 删除指定索引处元素
  42.      *
  43.      * @param index 索引
  44.      * @return 被删除元素
  45.      */
  46.     public int poll(int index) {
  47.         int deleted = array[index];
  48.         swap(index, size - 1);
  49.         size--;
  50.         down(index);
  51.         return deleted;
  52.     }
  53.  
  54.     /**
  55.      * 替换堆顶元素
  56.      *
  57.      * @param replaced 新元素
  58.      */
  59.     public void replace(int replaced) {
  60.         array[0] = replaced;
  61.         down(0);
  62.     }
  63.  
  64.     /**
  65.      * 堆的尾部添加元素
  66.      *
  67.      * @param offered 新元素
  68.      */
  69.     public void offer(int offered) {
  70.         if (size == array.length) {
  71.             grow();
  72.         }
  73.         up(offered);
  74.         size++;
  75.     }
  76.  
  77.     private void grow() {
  78.         int capacity = size + (size >> 1);
  79.         int[] newArray = new int[capacity];
  80.         System.arraycopy(array, 0,
  81.                 newArray, 0, size);
  82.         array = newArray;
  83.     }
  84.  
  85.     // 将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
  86.     private void up(int offered) {
  87.         int child = size;
  88.         while (child > 0) {
  89.             int parent = (child - 1) / 2;
  90.             boolean cmp = max ? offered > array[parent] : offered < array[parent];
  91.             if (cmp) {
  92.                 array[child] = array[parent];
  93.             } else {
  94.                 break;
  95.             }
  96.             child = parent;
  97.         }
  98.         array[child] = offered;
  99.     }
  100.  
  101.     public Heap(int[] array, boolean max) {
  102.         this.array = array;
  103.         this.size = array.length;
  104.         this.max = max;
  105.         heapify();
  106.     }
  107.  
  108.     // 建堆
  109.     private void heapify() {
  110.         // 如何找到最后这个非叶子节点  size / 2 - 1
  111.         for (int i = size / 2 - 1; i >= 0; i--) {
  112.             down(i);
  113.         }
  114.     }
  115.  
  116.     // 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
  117.     private void down(int parent) {
  118.         int left = parent * 2 + 1;
  119.         int right = left + 1;
  120.         int min = parent;
  121.         if (left < size && (max ? array[left] > array[min] : array[left] < array[min])) {
  122.             min = left;
  123.         }
  124.         if (right < size && (max ? array[right] > array[min] : array[right] < array[min])) {
  125.             min = right;
  126.         }
  127.         if (min != parent) { // 找到了更大的孩子
  128.             swap(min, parent);
  129.             down(min);
  130.         }
  131.     }
  132.  
  133.     // 交换两个索引处的元素
  134.     private void swap(int i, int j) {
  135.         int t = array[i];
  136.         array[i] = array[j];
  137.         array[j] = t;
  138.     }
  139.  
  140.     public Object getSize() {
  141.         return size;
  142.     }
  143.  
  144.  
  145.  
  146. }

-----

  1. import java.util.Comparator;
  2. import java.util.PriorityQueue;
  3.  
  4. /*
  5. 当然我们也可以不用自己定义的heap 在java中也有一个功能类似的类PriorityQueue 优先级队列
  6.  */
  7. public class E04Leetcode295 {
  8.     /**
  9.      * 为了保证两边数据量的平衡
  10.      *
  11.      * 两边个数一样时,左边个数+1
  12.      * 两边个数不一样时,右边个数+1
  13.      *
  14.      * 但是,随便一个数直接加入吗?
  15.      *
  16.      * 左边个数+1时,应该挑右边最小的加入
  17.      * 右边个数+1时,应该挑左边最大的加入
  18.      *
  19.      */
  20.     public void addNum(int num){
  21.         if(left.size()==right.size()){
  22.             right.offer(num);
  23.             left.offer(right.poll());
  24.         }else{
  25.             left.offer(num);
  26.             right.offer(left.poll());
  27.         }
  28.     }
  29.  
  30.  
  31.     /**
  32.      * 两边数据一致,左右各取堆顶元素平均
  33.      * 左边多一个,取左边堆顶元素
  34.      */
  35.     public double findMedian(){
  36.         if(left.size()== right.size()){
  37.             return (left.peek()+right.peek())/2.0;
  38.         }
  39.         else {
  40.             return left.peek();
  41.         }
  42.     }
  43.     //大顶堆
  44.     private PriorityQueue<Integer> left =new PriorityQueue<>(
  45.             (a,b)->Integer.compare(b,a)//-1 b<a  0 a==b 1 b>a
  46.     );
  47.     //比较器
  48.  
  49.     //小顶堆
  50.     private PriorityQueue<Integer> right =new PriorityQueue<>(
  51.             (a,b)->Integer.compare(a,b)//省略不写也一样 compare
  52.             //-1 a<b  0 a==b  1 a>b
  53.     );
  54.  
  55.     public static void main(String[] args) {
  56.         //这里就不去看源码了 以上浮为例,大概的实现逻辑
  57.         Comparator<Integer>cmp = (a,b)->Integer.compare(a,b);//小顶堆比较器compare -1 a<b,0 a==b,1 a>b
  58. //        Comparator<Integer>cmp = (a,b)->Integer.compare(b,a);//小顶堆比较器compare -1 b<a,0 a==b,1 b>a
  59.         int a = 10;//父元素值
  60.         int b =5;//新增元素值
  61.         if(cmp.compare(a,b)>0){
  62.             System.out.println("上浮");
  63.         }else{
  64.             System.out.println("停止上浮");
  65.         }
  66.     }
  67. }
  1. class MedianFinder {
  2.     PriorityQueue<Integer> queMin;
  3.     PriorityQueue<Integer> queMax;
  4.  
  5.     public MedianFinder() {
  6.         queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
  7.         queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
  8.     }
  9.     
  10.     public void addNum(int num) {
  11.         if (queMin.isEmpty() || num <= queMin.peek()) {
  12.             queMin.offer(num);
  13.             if (queMax.size() + 1 < queMin.size()) {
  14.                 queMax.offer(queMin.poll());
  15.             }
  16.         } else {
  17.             queMax.offer(num);
  18.             if (queMax.size() > queMin.size()) {
  19.                 queMin.offer(queMax.poll());
  20.             }
  21.         }
  22.     }
  23.     
  24.     public double findMedian() {
  25.         if (queMin.size() > queMax.size()) {
  26.             return queMin.peek();
  27.         }
  28.         return (queMin.peek() + queMax.peek()) / 2.0;
  29.     }
  30. }
  31.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/387294
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号