理解算法(1): 最大值，最小值，和堆。-526互联

最近总想，算法好像没有数学那样直观，例如方程可以解决一大类问题，我们遇到许多数学问题，只要将其转成方程问题，剩下的就是解方程。算法好像不是那么直观，顺着这个思路开始重新看算法问题。今天有一个收获，也可能其他人早就知道。

int max=INT_MIN;
for(size_t i=0;i<v.size();i++){
   if(v[i]>max){
       max=v[i];
   }
}

int min=INT_MAX;
for(size_t i=0;i<v.size();i++){
   if(v[i]<min){
       min=v[i];
   }
}

我今天才意识到，这里的
a）int max=INT_MIN; 和 if(v[i]>max)
b）int min=INT_MAX; 和 if(v[i]<min)

居然，分别就是隐含的堆。其中，
a) int max=INT_MIN; 是元素只有一个的最大堆。
b) int min=INT_MAX; 是元素只有一个的最小堆。

从这个角度来说，很多利用堆来解决的算法，本质上就和上面这两个for循环一样。

例如，求k个最小值：

// 步骤1，等价于 int min = INT_MAX;
MinHeap heap;
for(size_t i=0;i<k;i++){
  heap.push(v[i]);
}

// 步骤2，等价于 if(v[i]<min) 然后交换
for(size_t i=k;i<v.size();i++){
  if(v[i]<heap.top()){
      heap.pop();
      heap.push(v[i]);
  }
}

例如，求k个最大值

// 步骤1，等价于 int max = INT_MIN;
MaxHeap heap;
for(size_t i=0;i<k;i++){
  heap.push(v[i]);
}

// 步骤2，等价于 if(v[i]>max) 然后交换
for(size_t i=k;i<v.size();i++){
  if(v[i]>heap.top()){
      heap.pop();
      heap.push(v[i]);
  }
}

从这个角度来说，似乎：求最大值和最小值，就是堆问题。只是堆的元素可能是1个，也可能是k个，进一步堆每个元素可能是一个向量，就像方程和方程组的关系。

--end--