堆及其算法

偏执的太偏执、 2022-03-19 08:10 154阅读 0赞

堆一般是一种隐式表述（implicit representation），简单的说堆是由另外一种容器实现的。由于堆中的操作都基于搜寻父节点，子节点。如果用数组的话，那么不需要额外的存储空间就可以轻松实现。左子节点标号=父节点标号\*2+1；右子节点标号=父节点标号\*2+2；父节点标号=（子节点标号-1）/2。如果在用一种小技巧，将标号0处元素保留（或设为无限大（小）值），从而忽略根节点的话，计算式将改为左子节点标号 = 父节点标号\*2；右子节点标号 = 父节点标号\*2+1；父节点标号 = 子节点标号/2。另外堆要求数组长度动态，所以用vector实现。

接下来分析最大堆的各种操作（最小堆类似）。理解了上溯和下溯基本堆的操作都可以理解了。

push\_heap()是在一个最大堆中插入元素，元素先插在最尾端，然后进行上溯。所以复杂度为O（lgn）

\_\_adjust\_heap()这个函数维持最大堆的性质，进行下溯就可以了,而STL中不知道为什么最终的赋值采用了插入操作再做一次上溯。但不管怎么样复杂度为O（lgn）。但是这里还有个问题，为什么只进行下溯就可以了？因为\_\_adjust\_heap（）是个内部函数，客户端无法调用，看下面其他函数调用\_\_adjust\_heap()

的时刻就清楚了。

pop\_heap()弹出最大元素，实现的方式就是先保存尾元素值，然后根节点值赋给尾元素，根变为一个洞然后洞号和值（尾值）都有了，调用\_\_adjust\_heap()重整堆，这里必然是下溯，符合\_\_adjust\_heap()算法。所以复杂度为O（lgn）。注意pop\_heap()只是移动元素，并不弹出，要继续调用vector：：push\_back()。

make\_heap()建堆是在未排序的数组上进行的，由最后一个非叶子节点开始，循环调用\_\_adjust\_heap()此时是往上循环的，所以只要进行下溯，符合\_\_adjust\_heap()算法。这里要分析make\_heap()的复杂度，简单地想线性元素个数调用\_\_adjust\_heap()复杂度因为O（nlgn）。这是一个上界，但是不够精确，因为调用\_\_adjust\_heap()的节点高度不一样。这里要提到一个小性质：一个n元素堆的高度为lgn，在任意高度h上，至多有n/(2^h+1)（取上界）个节点。那么复杂度为n/(2^h+1)O(h)在0至lgn间求和，最终得O（n）。

sort\_heap()很简单，从头至尾循环调用pop\_heap()，复杂度O（nlgn）。

以下见STL源码，分析已有详细注释。

//以下这组 push_heap()不允许指定“大小比较标准”
    template <class RandomAccessIterator>
    inline void push_heap(RandomAccessIterator first, RandomAccessIterator last) {
      // 注意！！！此函数调用的时候，元素以至于容器尾端。
      __push_heap_aux(first, last, distance_type(first), value_type(first));
    }
    
    template <class RandomAccessIterator, class Distance, class T>
    inline void __push_heap_aux(RandomAccessIterator first,
                                RandomAccessIterator last, Distance*, T*) {
      __push_heap(first, Distance((last - first) - 1), Distance(0), 
                  T(*(last - 1)));
      // 以上根据 implicit representation heap 的结构特性：新值必至于底层
      // 容器的最尾端，此即第一个洞号：(last-first)–1。
    }
    
    template <class RandomAccessIterator, class Distance, class T>
    void __push_heap(RandomAccessIterator first, Distance holeIndex,
                     Distance topIndex, T value) {
      Distance parent = (holeIndex - 1) / 2;	// 父节点标号
      while (holeIndex > topIndex && *(first + parent) < value) {
        // 尚未到达顶端且父节点值小于新值（这不符合最大堆的特性）
        // 由于以上使用 operator<，可知 STL heap 是一种max-heap
        *(first + holeIndex) = *(first + parent);	
        holeIndex = parent; // 上溯：父节点标号为洞号
        parent = (holeIndex - 1) / 2;	// 新洞的父节点标号
      }    // 持续至顶端或满足最大堆特性为止。
      *(first + holeIndex) = value;	// 另洞值为新值，完成拆入操作。
    }
    
    // 以下这组 push_heap()允许指定“大小比较标准”
    template <class RandomAccessIterator, class Compare>
    inline void push_heap(RandomAccessIterator first, RandomAccessIterator last,
                          Compare comp) {
      __push_heap_aux(first, last, comp, distance_type(first), value_type(first));
    }
    
    template <class RandomAccessIterator, class Compare, class Distance, class T>
    inline void __push_heap_aux(RandomAccessIterator first,
                                RandomAccessIterator last, Compare comp,
                                Distance*, T*) {
      __push_heap(first, Distance((last - first) - 1), Distance(0), 
                  T(*(last - 1)), comp);
    }
    
    template <class RandomAccessIterator, class Distance, class T, class Compare>
    void __push_heap(RandomAccessIterator first, Distance holeIndex,
                     Distance topIndex, T value, Compare comp) {
      Distance parent = (holeIndex - 1) / 2;
      while (holeIndex > topIndex && comp(*(first + parent), value)) {
        *(first + holeIndex) = *(first + parent);
        holeIndex = parent;
        parent = (holeIndex - 1) / 2;
      }
      *(first + holeIndex) = value;
    }
    
    
    
    // 以下这个 __adjust_heap()不允许指定“大小比较标准”
    template <class RandomAccessIterator, class Distance, class T>
    void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
                       Distance len, T value) {
      Distance topIndex = holeIndex;
      Distance secondChild = 2 * holeIndex + 2;// 洞节点右子节点标号
      while (secondChild < len) {
        // 比较洞节点的左右子节点值，选出较大子节点
        if (*(first + secondChild) < *(first + (secondChild - 1)))
          secondChild--; //左子结点大，洞号为左子结点标号
        // Percolate down：另较大值为洞值，再令洞号下移为较大值标号
        *(first + holeIndex) = *(first + secondChild);  
        holeIndex = secondChild;
        // 找出新洞结点的右子节点
        secondChild = 2 * (secondChild + 1);
      }
    if (secondChild == len) { // 因为secondChild为标号，而标号等于长度的话
      //那么就是该洞节点无右子结点但有左子结点
        // Percolate down
        *(first + holeIndex) = *(first + (secondChild - 1));
        holeIndex = secondChild - 1;
      }
    // 将欲调整值填入洞号内。
    //!!!!!!注意，此时肯定满足次序特性。
    //下面直接改为 *(first + holeIndex) = value; 应该可以。
    //这里__push_heap的话还要进行一次上溯
      __push_heap(first, holeIndex, topIndex, value);
    }
    
    // 以下这个 __adjust_heap()允许指定“大小比较标准”
    template <class RandomAccessIterator, class Distance, class T, class Compare>
    void __adjust_heap(RandomAccessIterator first, Distance holeIndex,
                       Distance len, T value, Compare comp) {
      Distance topIndex = holeIndex;
      Distance secondChild = 2 * holeIndex + 2;
      while (secondChild < len) {
        if (comp(*(first + secondChild), *(first + (secondChild - 1))))
          secondChild--;
        *(first + holeIndex) = *(first + secondChild);
        holeIndex = secondChild;
        secondChild = 2 * (secondChild + 1);
      }
      if (secondChild == len) {
        *(first + holeIndex) = *(first + (secondChild - 1));
        holeIndex = secondChild - 1;
      }
      __push_heap(first, holeIndex, topIndex, value, comp);
    }
    // 以下这组pop_heap()不允许指定“大小比较标准”
    template <class RandomAccessIterator>
    inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last) {
      __pop_heap_aux(first, last, value_type(first));
    }
    
    template <class RandomAccessIterator, class T>
    inline void __pop_heap_aux(RandomAccessIterator first,
                               RandomAccessIterator last, T*) {
      __pop_heap(first, last-1, last-1, T(*(last-1)), distance_type(first));
      // 以上，根据 implicit representation heap 的次序特性，pop动作的结果
      // 应为底层容器的第一个值（标号0的根节点）。因此，首先设定欲调整的值是尾值，然後將首值调至
    // 尾节点（所以以上将迭代器result设为last-1）。然后重整 [first, last-1)。这里有个细节
    // 因为最后要重整，需要传入重整节点值，第四个参数，生成了一个原堆尾节点值的临时变量！！
    }
    
    template <class RandomAccessIterator, class T, class Distance>
    inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                           RandomAccessIterator result, T value, Distance*) {
      *result = *first; //设定尾值为根节点值，即为欲求结果
    // pop_heap是没有返回值的。之后可由客户端以底层容器的pop_back() 取出尾值。
      __adjust_heap(first, Distance(0), Distance(last - first), value);
      // 以上重新调整 heap，洞号为 0（根节点），欲调整值为value（原尾值）。
    }
    
    
    // 以下这组 __pop_heap()允许指定“大小比较标准”
    template <class RandomAccessIterator, class T, class Compare, class Distance>
    inline void __pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                           RandomAccessIterator result, T value, Compare comp,
                           Distance*) {
      *result = *first;
      __adjust_heap(first, Distance(0), Distance(last - first), value, comp);
    }
    
    template <class RandomAccessIterator, class T, class Compare>
    inline void __pop_heap_aux(RandomAccessIterator first,
                               RandomAccessIterator last, T*, Compare comp) {
      __pop_heap(first, last - 1, last - 1, T(*(last - 1)), comp,
                 distance_type(first));
    }
    
    template <class RandomAccessIterator, class Compare>
    inline void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
                         Compare comp) {
        __pop_heap_aux(first, last, value_type(first), comp);
    }
    
    // 以下这组 make_heap()不允许指定“大小比较标准”。
    // 将 [first,last) 排列为一个max-heap。
    template <class RandomAccessIterator>
    inline void make_heap(RandomAccessIterator first, RandomAccessIterator last) {
      __make_heap(first, last, value_type(first), distance_type(first));
    }
    
    template <class RandomAccessIterator, class T, class Distance>
    void __make_heap(RandomAccessIterator first, RandomAccessIterator last, T*,
                     Distance*) {
      if (last - first < 2) return;	// 如果長度為 0 或 1，不必重新排列。
      Distance len = last - first;
    //找出第一個需要重排的子樹頭部，以 parent 標示出。
    //由于任何叶子节点都不需执行下溯
      //所以有以下计算，parent 命名不佳，名为 holeIndex 更好。
      Distance parent = (len - 2)/2; 
    //为什么是这个算式？？由于STL中第一个节点的标号为0，所以求节点的父节点算式为（n-1）/2，
    //而这里len为长度，len-1是最后一个叶子节点的标号。
      while (true) {
        // 重排以parent为首的子树。len 是为了让 __adjust_heap() 判断操作范围
        __adjust_heap(first, parent, len, T(*(first + parent)));
        if (parent == 0) return;	// 走完根节点，就结束。
        parent--;					
      }
    }
    
    
    // 以下这组 make_heap()允许指定“大小比较标准”。
    template <class RandomAccessIterator, class Compare>
    inline void make_heap(RandomAccessIterator first, RandomAccessIterator last,
                          Compare comp) {
      __make_heap(first, last, comp, value_type(first), distance_type(first));
    }
    
    template <class RandomAccessIterator, class Compare, class T, class Distance>
    void __make_heap(RandomAccessIterator first, RandomAccessIterator last,
                     Compare comp, T*, Distance*) {
      if (last - first < 2) return;       
      Distance len = last - first;
      Distance parent = (len - 2)/2;
        
      while (true) {
        __adjust_heap(first, parent, len, T(*(first + parent)), comp);
        if (parent == 0) return;
        parent--;
      }
    }
    
    
    // 以下这个 sort_heap()不允许指定“大小比较标准”
    template <class RandomAccessIterator>
    void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
      // 以下，每执行一次 pop_heap()，极值（在STL heap中为极大值）即被放在尾端。
      // 扣除尾端再执行一次 pop_heap()，次极值又被放在新尾端。一直下去，最后即得
      // 排序结果。
      while (last - first > 1)
         pop_heap(first, last--); // 每执行 pop_heap() 一次，操作范围即退缩一格。
    }
    
    // 以下这个 sort_heap()允许指定“大小比较标准”
    template <class RandomAccessIterator, class Compare>
    void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
                   Compare comp) {
      while (last - first > 1)
         pop_heap(first, last--, comp);
    }