堆一般是一种隐式表述(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);
}


 

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐