关于堆:堆优先队列进阶TopK3D接雨水CJsRust语言描述

1 前言

在之前的文章里，我分享了 Js 版的堆实现和 C 语言版的堆实现, 了解的话，堆的实现其实并不难，以大顶堆为例，简略演绎就是插入时候，比节点小，就一直向下沉，让更大的上浮，直到最大的上浮到根节点。

1. 数据与构造与算法: 堆 C 语言形容

2. 数据结构与算法: 堆 优先队列 JavaScript 语言形容

优先队列基于堆实现，顾名思义是一个有优先级的队列，最高优先级的最先出列，低优先级最初出列（如果是最小堆则刚好相同）。明天咱们就用堆和优先队列高效解决一些问题，别离是经典的 TopK 问题 - 堆解法，以及 3D 接雨水 - 优先队列解法。

2 TopK问题 - 堆解法

题目：215. 数组中的第 K 个最大元素

2.1 思路

在之前的文章里，我分享了基于 Partition 和ThreePartition算法的原地排序，来高效求解 TopK 问题，原地排序，没有应用额定的空间，空间复杂度很低，然而工夫复杂度稳定比拟大，如果随机取的基准值很现实，那么效率超高，但如果数组里值散布很发散，随机取的基准值也很不现实，那么这种极其状况下，那么效率就不是很高, 尽管《算法导论》证实了 Partition 算法是近似线性，但其线性常数项相对比 1 大多了；

而堆解法呢，就是稳固的工夫空间复杂度，建堆的最差复杂度是确定的，遍历一遍的复杂度只有O(N), 能够确定在kLog(k) + O(N)。

2.2 C语言形容

先建设一个容量为 k 的最小堆，后续的元素，只有比堆顶大的，才入堆，否则间接略过，最初堆顶元素就是第 K 大元素。

typedef struct MinHeap {
    int *data; // 数据域
    int size; // 长度
    int max;// 最大长度
} MinHeap;
void insert(struct MinHeap *p, int item){if (p->size == p->max)
    {printf("******:\n");
        return;
    }
    int i = ++p->size;
    for (; p->data[i/2] > item; i/=2)
    {if (i <= 1)
        {break;}
        p->data[i] = p->data[i/2];
    }
    p->data[i] = item;
}
void delete(struct MinHeap *p){p->data[1] = p->data[p->size--];
    int i = 1;
    int tmp;
    while(2*i <= p->size){
        // 如果有右节点
        if (2*i + 1 <= p->size)
        {if (p->data[2*i + 1] < p->data[i] || p->data[2*i] < p->data[i])
            {if (p->data[2*i + 1] < p->data[2*i])
                {tmp              = p->data[i];
                    p->data[i]       = p->data[2*i + 1];
                    p->data[2*i + 1] = tmp;
                    i          = 2*i + 1;
                }else{tmp              = p->data[i];
                    p->data[i]       = p->data[2*i];
                    p->data[2*i] = tmp;
                    i          = 2*i;
                }
            }else{return;}

        }else{
            // 只有左节点
            if (p->data[2*i] < p->data[i])
            {tmp              = p->data[i];
                p->data[i]       = p->data[2*i];
                p->data[2*i] = tmp;
                i                  = 2*i;
            }else{return;}
        }
    }
}

int findKthLargest(int* nums, int numsSize, int k){
    struct MinHeap *heap;
    heap=(struct MinHeap *)malloc(sizeof(struct MinHeap));
    if (heap == NULL)
    {printf("malloc error \n");
    return 0;
    }
    heap->size = 0;
    heap->max  = k + 1;
    heap->data = (int*)malloc(sizeof(int)*heap->max);
    if(heap->data == NULL)
    {printf("malloc error \n");
    return 0;
    }
    heap->data[0] = 9999;
    for (int i = 0; i < numsSize; ++i)
    {if(i < k){insert(heap, nums[i]);
        }else{if(nums[i] > heap->data[1]){delete(heap);
                insert(heap, nums[i]);
            }
        }
    }
    return heap->data[1];
}

3 3D接雨水 - 优先队列解法

题目：407. 接雨水 II

3.1 思路

之前在枯燥栈进阶里分享过 2D 接雨水，那个尽管是 hard 但比较简单;3D接雨水思考的比 2D 多了些，不能只思考两边的高度，而是要思考周围，只有周围都比本人高，能力接得住雨水；思路呢其实就是把最外围的记录下来，扔到优先队列里 (小堆)，而后一直让堆顶出队，去更新堆顶元素的周围，而后把周围的入堆，如果周围的元素有比堆顶还低的，显然能够接到雨水。PS: 感觉我解说的必定没有题解清晰，倡议看题解。
## 3.2 Js语言形容

 var Heap = function () {this.data = []
  this.insert = (obj) => {
      let i = this.data.length
      for (; i > 0 && this.data[Math.floor((i - 1) / 2)].val >= obj.val; i = Math.floor((i - 1) / 2)) {if (i < 1) {break}
          this.data[i] = this.data[Math.floor((i - 1) / 2)]
      }
      this.data[i] = obj
  }
  this.pop = () => {if (this.data.length == 0) {return null}
      if (this.data.length == 1) {return this.data.pop()
      }
      let top = this.data[0]
      this.data[0] = this.data.pop()

      let i = 0
      while (2 * i + 1 < this.data.length) {if (2 * i + 2 < this.data.length) {if (this.data[2 * i + 2].val < this.data[i].val || this.data[2 * i + 1].val < this.data[i].val) {if (this.data[2 * i + 2].val < this.data[2 * i + 1].val) {this.swap(i, 2 * i + 2)
                      i = 2 * i + 2
                  } else {this.swap(i, 2 * i + 1)
                      i = 2 * i + 1
                  }
              } else {break}
          } else {if (this.data[2 * i + 1].val < this.data[i].val) {this.swap(i, 2 * i + 1)
                  i = 2 * i + 1
              } else {break}
          }
      }
      return top
  }
  this.swap = (i, j) => {let tmp = this.data[j]
      this.data[j] = this.data[i]
      this.data[i] = tmp
  }
};

3.3 Rust语言形容

思路都是一样的，仅仅语言不同

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Copy, Clone, Eq, PartialEq)]
struct Item {
    val: i32,
    i: usize,
    j: usize,
}

impl Ord for Item {fn cmp(&self, other: &Self) -> Ordering {other.val.cmp(&self.val)
    }
}

impl PartialOrd for Item {fn partial_cmp(&self, other: &Self) -> Option<Ordering> {Some(self.cmp(other))
    }
}
impl Solution {pub fn trap_rain_water(height_map: Vec<Vec<i32>>) -> i32 {let h = height_map.len();
        let w = height_map[0].len();
        if h <= 2 || w <= 2 {return 0;}

        let mut water = vec![vec![-1; w]; h];
        let mut pq: BinaryHeap<Item> = BinaryHeap::new();

        let mut i = 0;
        while i < h {water[i][0]     = height_map[i][0];
            water[i][w - 1] = height_map[i][w - 1];
            pq.push(Item {val: height_map[i][0],
                i: i,
                j: 0,
            });
            pq.push(Item {val: height_map[i][w - 1],
                i: i,
                j: w - 1,
            });
            i += 1;
        }
        i = 1;
        while i < w - 1 {water[0][i]         = height_map[0][i];
            water[h - 1][i]     = height_map[h - 1][i];
            pq.push(Item {val: height_map[0][i],
                i: 0,
                j: i,
            });
            pq.push(Item {val: height_map[h - 1][i],
                i: h - 1,
                j: i
            });
            i += 1;
        }
        let dirs :[i32;5] = [-1, 0, 1, 0, -1];
        let mut res = 0;
        let mut k;
        while pq.len() > 0 {if let Some(Item { val, i, j}) = pq.pop() {
                k = 0;
                while k < 4 {let nx = (i as i32 + dirs[k])   as usize;
                    let ny = (j as i32 + dirs[k+1]) as usize;
                    if 0 < nx && nx < h as usize && 0 < ny && ny < w && water[nx][ny] == -1 {if height_map[nx][ny]  < val {res += val - height_map[nx][ny];
                        }
                        water[nx][ny] = val;
                        pq.push(Item {val: val.max(height_map[nx][ny]),
                            i: nx,
                            j: ny
                        });
                    }
                    k += 1;
                }
            }
        }
        return res;
    }
}