数据结构之堆

概念

堆是一种有效的优先队列，对于二叉堆而言，有最大堆与最小堆。最大堆的性质是所有节点满足A[Parent[i]]>=A[i]，最小堆相反。

《算法导论》里给出了最大堆的几种操作：

• Max-Heapify 当有节点不满足大于子节点特性时，进行下沉，时间复杂度O(lgn)，是维护最大堆性质的重要过程。
• Build-Max-Heap 建堆过程，具有线性时间复杂度。
• Heapsort 即堆排序
• Max-Heap-Insert、Heap-Extract-Max、Heap-Increment-Key和Heap-Maximum分别对应插入元素、返回并去掉最大值、将元素值增加到指定值和返回最大值的过程。

堆的下沉

节点3的下沉过程

对于某一节点而言，如果违背最大堆性质，则与子节点中的较大值进行交换，递归该过程，直到满足性质为止。

建堆

对于已经存在的数组而言，可以自底向上对非叶节点(n/2-1)进行下沉，时间复杂度O(n)；或者依次对空堆插入每个元素来建堆。

堆排序

依次取出顶部元素，最后一个元素放在顶部，然后进行下沉，一直到最大堆为空。

常用操作

返回最大值：返回堆顶元素值即可
返回并去掉最大值：将最后一个元素与顶部元素交换，进行一次下沉，返回顶部元素值。
插入：在最后位置放入该元素，先上浮（找到适合插入的位置），再下沉
删除：将该元素与最后一个元素交换，先上浮（找到适合插入的位置），再下沉
将元素值增加到指定值：先将节点上浮（找到适合插入的位置），再下沉

LeetCode之堆

373.Find K Pairs with Smallest Sums
给定两个已升序排列数组nums1、nums2与数字k，返回k个和最小的pair(nums1[i],nums2[j])
Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Return: [1,2],[1,4],[1,6]

分析：该题目除了暴力破解，乍一看思路放在找到当前和最小的对后，在元素附近找，但是怎么想也没有得出所以然。看了下forum中讨论，将两个数组分别作为行列，对应的和作为二维数组，那么这道题就立即转化为378.Kth Smallest Element in a Sorted Matrix。

      2   4   6
   +------------
 1 |  3   5   7
 7 |  9  11  13
11 | 13  15  17

由于和矩阵的性质：每一行与每一列都是升序排列的，将第一行建立最小堆后，每次取出堆顶元素则插入下一行同列元素（有可能小于堆内元素），再取出堆顶，进行k次则得到k个最小的和对应的数对。

var Heap = require('./BinaryHeap');

var kSmallestPairs = function (nums1, nums2, k) {
  var res = [];
  if (nums1.length === 0 || nums2.length === 0) return res;
  var rowLen = nums1.length, colLen = nums2.length;
  //get sum matrix
  var sumMatrix = [];
  for (var row = 0; row < rowLen; row++) {
    sumMatrix.push(new Array(colLen));
    for (var col = 0; col < colLen; col++) {
      sumMatrix[row][col] = nums1[row] + nums2[col];
    }
  }
  //build heap
  var minHeap = new Heap(function (x) {
    return x[0];
  });
  for (col = 0; col < colLen; col++) {
    minHeap.push([sumMatrix[0][col], 0, col]);
  }
  //get k minimum numbers
  var min;
  k = Math.min(k, rowLen * colLen);
  while (k-- > 0) {
    min = minHeap.pop();
    res.push([nums1[min[1]], nums2[min[2]]]);
    if (min[1] + 1 < rowLen) {
      minHeap.push([sumMatrix[min[1] + 1][min[2]], min[1] + 1, min[2]]);
    }
  }
  return res;
};

253.Meeting Rooms II
给定包含一天内时间段的数组，时间段可能交叉，返回最少需要的会议室。
Input: [[0, 30],[5, 10],[15, 20]],
Output: 2.

分析：按照起始时间对时间间隔排序后，可以得到下列在时间轴上排列的数。

以结束时间为关键字建立最小堆，若新的起始时间大于等于最小结束时间，则不需加会议室，最小结束时间替换为新的结束时间；否则需要加会议室，并将该结束时间入堆。

var Heap = require('./BinaryHeap');
var roomNum = function (intervals) {
  intervals.sort(function (interval1, interval2) {
    return interval1[0] - interval2[0];
  });
  var minHeap = new Heap(function (x) {
    return x;
  });
  minHeap.push(intervals[0][3]);
  var res = 1;
  for (var i = 1; i < intervals.length; i++) {
    var minEnd = minHeap.pop();
    if (intervals[i][0] >= minEnd) {
      minEnd = intervals[i][4];
    } else {
      res++;
      minHeap.push(intervals[i][5]);
    }
    minHeap.push(minEnd);
  }
  return res;
};

407. Trapping Rain Water II
     给定二维数组，数值表示每点的高度，返回该数组能容纳的最多的水。
     Input: [[1,4,3,1,3,2],
     [3,2,1,3,2,4],
     [2,3,3,2,3,1]]
     Output: 4
     

与一维的Trapping Water类似，分别从边界向中间维护最小值，用最小值的较大减去该值则为该点能容纳的水。

var Heap = require('./BinaryHeap');

var trapRainWater = function (heightMap) {
  if (!heightMap || heightMap.length < 1 || heightMap[0].length < 1) return 0;
  //build min heap with the four borders
  var row = heightMap.length, col = heightMap[0].length;
  var used = [];
  for (i = 0; i < row; i++) {
    used.push(new Array(col).fill(false));
  }
  //heap element (i,j,height)
  var minHeap = new Heap(function (x) {
    return x[2];
  });
  for (var i = 0; i < row; i++) {
    minHeap.push([i, 0, heightMap[i][0]]);
    minHeap.push([i, col - 1, heightMap[i][col - 1]]);
    used[i][0] = used[i][col - 1] = true;
  }
  for (i = 1; i < col - 1; i++) {
    minHeap.push([0, i, heightMap[0][i]]);
    minHeap.push([row - 1, i, heightMap[row - 1][i]]);
    used[0][i] = used[row - 1][i] = true;
  }
  //iterate from border to center
  var res = 0, moves = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  for (i = 0; i < row; i++) {
    for (var j = 0; j < col; j++) {
      var minHeight = minHeap.pop();
      for (var k = 0; k < moves.length; k++) {
        var x = minHeight[0] + moves[k][0], y = minHeight[1] + moves[k][1];
        if (x > -1 && x < row && y > -1 && y < col && !used[x][y]) {
          if (minHeight[2] > heightMap[x][y]) {
            res += minHeight[2] - heightMap[x][y];
            minHeap.push([x, y, minHeight[2]]);
          } else {
            minHeap.push([x, y, heightMap[x][y]]);
          }
          used[x][y] = true;
        }
      }
    }
  }
  return res;
};