堆、堆排序以及TopK问题

堆的定义

堆是一种特殊的数据结构，可以形象化的看成一颗完全二叉树，一般内部的存储结构为数组；堆中的某个节点总是不大于或者（不小于）其左右节点，其中前者为成为小顶堆（最小堆，堆顶为最小值），后者成为大顶堆（最大堆，堆顶为最大值）

堆的一些操作

• build: 建立一个堆
• insert: 往堆中插入一个新节点
• update: 更新某个节点的值, 根据节点的新值重新调整堆，使其符合堆的特性
• get_top : 获取堆顶的节点
• delete_top : 删除堆顶的节点, 然后重新调整堆，使其满足堆的特性

下面以最大堆为例进行堆操作的说明

• 建堆

  • 自上到下构建堆

    • 自上到下构建堆的流程是：假定数组arr的前i个节点已经满足堆的特性，然后新增一个节点arr[i]到数组尾,调整堆使得数组arr[0~i]满足堆的特性；当i = n -1（n是数组长度）时，则建堆完毕；
    • 新增节点arr[i]到数组尾，调整的过程：可以形象的描述为，该节点沿着到根节点的二叉树路径，进行上浮；如果该节点比其父节点大，则将该节点和父节点进行交换，然后将当前节点设置为其父节点继续进行上浮比较；如果该节点比其父节点小，则停止上浮；直到该节点上浮到根节点，则本次上浮调整结束
    • 代码示例

      struct max_heap_t {
      int32_t* arr;
      int32_t  n;
      
      max_heap_t (int32_t* input_arr, int32_t arr_size){
          arr = new int32_t[arr_size];
          memcpy(arr, input_arr, sizeof(int32_t) * arr_size);
          n = arr_size;
      }
      
      ~max_heap_t () {
          if (arr) {
              delete[] arr;
              arr = nullptr;
          }
      }
      
      /** time complexity => O(nlogn) */
      void    build_heap_from_top_to_bottom() {
        
          for (int32_t i = 1; i < n; i++) {
             heap_ajust_from_bottom_to_top(i);
          }
      }
      
      /* O(logn) */
      void    heap_ajust_from_bottom_to_top(int32_t bottom_index) {
          int32_t tmp = arr[bottom_index];
          while (bottom_index > 0) {
              int32_t parent_index = (bottom_index - 1) / 2;
              if (arr[parent_index] < tmp ) {
                  arr[bottom_index] = arr[parent_index];
                  bottom_index = parent_index;
              }
              else {
                  break;
              }
          }
          arr[bottom_index] = tmp;
      }
      

    • 时间复杂度
      每次上浮调整的时间复杂度为O(logn), 总共要调整n-1次，所以建堆的时间复杂度为 O(nlogn)

  • 自下到上构建堆

    • 自下到上构建堆的流程是： 从最后一个节点的父节点开始一直到到根节点，逐步进行以选中节点为起点，进行下沉调整；到根节点下沉调整结束，则建堆完毕
    • 下沉调整的过程，可以描述为：从当前节点以及其左右子节点中选出最大的一个节点，如果最大节点是该节点本身，则下沉调整结束；如果是其左子节点（或者右子节点），则将该节点与其左子节点（或者其右子节点）交换，然后将当前节点设置为其左子节点（后后者右子节点）继续下浮比较；
    • 代码示例

       /* O(n) */
      void    build_heap_from_bottom_to_top() {
          int32_t max_index = n - 1;
          for (int32_t i = (max_index - 1) / 2; i >= 0; i--) {
              heap_adjust_from_top_to_bottom(i, max_index);
          }
      }
      
      /* O(logn) */
      void    heap_adjust_from_top_to_bottom(int32_t top_index, int32_t bottom_index) {
          int32_t tmp = arr[top_index];
          while (top_index <= (bottom_index - 1) / 2) {
              int32_t max_one = tmp;
              int32_t child_idx = 0;
              int32_t left_child_idx = top_index * 2 + 1;
              int32_t right_child_idx = top_index * 2 + 2;
              
              if (left_child_idx <= bottom_index && max_one < arr[left_child_idx] ) {
                  max_one = arr[left_child_idx];
                  child_idx = left_child_idx;
              }
              if (right_child_idx <= bottom_index && max_one < arr[right_child_idx] ) {
                  max_one = arr[right_child_idx];
                  child_idx = right_child_idx;
              }
            
              if (max_one != tmp) {
                  arr[top_index] = max_one;
                  top_index = child_idx;
              }
              else {
                  break;
              }
          }
          arr[top_index] = tmp;
      }
      
      

    • 时间复杂度
      自下到上建堆的时间复杂度是O(n)
      证明方法如下：

      假定节点个数为n， 叶子高度为h = log2(n)
      1. 假设根节点的高度为0，叶子节点高度为h，那么每层包含的元素个数为2^x，x从0到h。
      2. 构建堆的过程是自下而上，对于每层非叶子节点需要调整的次数为h-x，因此很明显根节点需要调整(h- 0)次，第一层节点需要调整(h-1)次，最下层非叶子节点需要调整1次。
      3. 因此可知，构造树高为h的二叉堆精确时间复杂度为：
      s = 12^(h-1) + 22^{(h-2)+……+h*2}0
      可以看出以上公式是等差数列和等比数列乘积之和，可以通过错位相减求：
      2s = 2^h + 22^(h-1)+32^{(h-2)+……+h*2}1
      因此可得:
      s = 2s -s = 2^h + 2^(h-1) + 2^(h-2) +…… + 2^1 - h
      最终可以通过等比数列公式进行计算得到s = 2*2^h - 2 -h
      将代入的s = 2n - 2 - log2(n)，近似的时间复杂度就是O(n)
      转载自: https://blog.csdn.net/hupenghui1224/article/details/57427045

堆排序

堆排序的话，无需额外的空间，直接可以在原堆内数组上进行堆排序；

• 堆排序的过程: 对于给定的数组arr以及长度n，首先根据该数组，构建堆；然后依次将当前数组尾元素arr[i]( i => n -> 0)与堆顶元素交换，然后重新调整堆(从 arr[0] ~ arr[i - 1])；一直到当前i = 0, 则排序完成；
• 代码实例:

    void    sort() {
  
        // build  heap first
        build_heap_from_bottom_to_top();
  
        // sort
        int32_t tmp = 0;
        for (int32_t i = n - 1; i > 0;) {
            // move heap top to end
            tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
  
            // adjust the heap
            heap_adjust_from_top_to_bottom(0, --i);
        }
    }
  

TopK问题

TopK问题描述：在N个无序元素中，找到最大的K个（或最小的K）

按照一般排序算法来寻找的话，时间复杂度为O(nlogn) + O(k); 当N很大，而K很小的时候，这种方法很慢；
可以采用堆来解决这个问题；下面以找到最大的K个值为例

• 算法流程：取该数组的前K个元素，构建一个最小堆；然后从该无序数组的第k个元素开始，一直到数组尾，遍历该数组，将当前元素与最小堆的堆顶元素比较，如果当前元素大于堆顶元素（最大的K个值里面的最小的那个），那么可以认为当前元素可能是要寻找的最大的K个元素之一，则将当前元素替换堆顶，然后重新进行堆调整；当遍历结束的时候，最小堆中的K个元素就是要寻找的最大的K个元素

• 代码示例

  void top_k(int32_t* input_arr, int32_t n, int32_t k) {
      printf("input array: (%d)\n", n);
      for (int32_t i = 0; i < n; ++i) {
          printf(", %d", input_arr[i]);
      }
      printf("\n");
      
      // O(k)
      // we suppose the k element of the min heap if the default top k element
      min_heap_t min_heap(input_arr, k);
      min_heap.build_heap_from_bottom_to_top();
      
      for (int32_t i = k; i < n; ++i) {
          // compare each element with the min element of the min heap
          // if the element > the min element of the min heap
          // we think may be the element is one of what we wanna to find in the top k
          if (input_arr[i] > min_heap.arr[0]){
              // swap
              min_heap.arr[0] = input_arr[i];
              
              // heap adjust
              min_heap.heap_adjust_from_top_to_bottom(0, k - 1);
          }
      }
      
      printf("top k: (%d)\n", k);
      min_heap.print_arr();
  }
  

• 算法复杂度
  创建初始堆的过程O(KlogK), 每次堆调整的时间复杂度O(logK), 寻找最大K个值的过程(N-K) * O(logK) = O((N-K)logK), 总得时间复杂度O(NlogK)