堆一般是一种隐式表述（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
向您推荐>>Eolink开发者社区

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

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生