STL之容器适配器（heaps）

用户9831583

发布于 2022-06-16 14:39:26

2540

发布于 2022-06-16 14:39:26

文章被收录于专栏：码出名企路

堆的底层实现是完全二叉树：每个节点与其子节点位置相对。父节点总是大于或等于子节点，这种情况下被叫作大顶堆，或者父节点总是小于或等于子节点，这种情况下叫作小顶堆。

注意：给定父节点的子节点不一定按顺序排列。

初始化：

max_heap() 对随机访问迭代器指定的一段元素重新排列，生成一个堆。默认使用的是 < 运算符，可以生成一个大顶堆。

  std::vector<double> numbers{2.5,10.0,3.5,6.5,8.0,12.0,1.5,6.0};
  std::make_heap(std::begin(numbers), std::end(numbers));
      //{12 10 3.5 6.5 8 2.5 1.5 6}

     std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
    std::make_heap(std::begin(numbers), std::end(numbers), std::greater<>());
     //{1.5 6 2.5 6.5 8 12 3.5 10}

添加元素：

    std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
    std::make_heap(std::begin(numbers),std::end(numbers));//{12 10 3.5 6.5 8 2.5 1.5 6}
    numbers.push_back(11); // {12 10 3.5 6.5 8 2.5 1.5 6 11}
    std::push_heap(std::begin(numbers), std::end(numbers));//{12 11 3.5 10 8 2.5 1.5 6 6.5}

自定义函数添加：

    std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
    std::make_heap(std::begin(numbers), std::end(numbers), std::greater<>());//{1.5 6 2.5 6.5 8 12 3.5 10}
    numbers.push_back(1.2);//{1.5 6 2.5 6.5 8 12 3.5 10 1.2}
    std::push_heap(std::begin(numbers), std::end(numbers),std::greater<>());//{1.2 1.5 2.5 6 8 12 3.5 10 6.5}

删除元素：

删除最大元素和添加元素到堆的过程有些相似，但所做的事是相反的。首先调用 pop_heap()，然后从容器中移除最大的元素。

std::vector<double> numbers{2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers));//{12 10 3.5 6.5 8 2.5 1.5 6}
std::pop_heap(std::begin(numbers),std::end(numbers));//{10 8 3.5 6.5 6 2.5 1.5 12}
numbers.pop_back();//{10 8 3.5 6.5 6 2.5 1.5}

pop_heap() 函数将第一个元素移到最后，并保证剩下的元素仍然是一个堆。然后就可以使用 vector 的成员函数 pop_back() 移除最后一个元素。

自定义函数删除：

std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers),std::greater<>());//{1.5 6 2.5 6.5 8 12 3.5 10}
std::pop_heap(std::begin(numbers), std::end(numbers),std:: greater<>());//{2.5 6 3.5 6.5 8 12 10 1.5}
numbers.pop_back();//{2.5 6 3.5 6.5 8 12 10}

因为可能会打乱容器中的堆， STL 提供了一个检查序列是否仍然是堆的方法：

if(std::is_heap(std::begin(numbers),std::end(numbers)))  
std::cout << "Great! We still have a heap.\n";
else    
std::cout << "oh bother! We messed up the heap.\n";

如果元素段是堆，那么 is_heap() 会返回 true。这里是用默认的比较断言 less<> 来检查元素顺序。如果这里使用的是用 greater<> 创建的堆，就会产生错误的结果。

为了得到正确的结果，表达式需要写为：

std::is_heap(std::begin(numbers),std::end(numbers),std::greater<>()

甚至可以更深入地检查元素中是否有部分元素为堆：

std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers),std::greater<>());// {1.5 6 2.5 6.5 8 12 3.5 10}
std::pop_heap (std::begin (numbers),std::end(numbers),std::greater<>());//{2.5 6 3.5 6.5 8 12 10 1.5}
auto iter =std::is_heap_until(std::begin(numbers),std::end(numbers),std::greater<>());
if(iter != std::end(numbers))    
std::cout << "numbers is a heap up to "<< *iter << std::endl;

is_heap_until() 函数返回一个迭代器，指向第一个不在堆内的元素。这个代码段会输出最后一个元素的值 1.5，因为在调用 pop_heap() 后，这个元素就不在堆内了。

STL 提供 sort_heap()会将元素段作为堆来排序。如果元素段不是堆，程序会在运行时崩溃。迭代器指向一个假定的大顶堆(用 less<> 排列)，然后将堆中的元素排成降序。结果当然不再是大顶堆。

std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers));//{12 10 3.5 6.5 8 2.5 1.5 6}
std::sort_heap(std::begin(numbers), std::end(numbers));//{1.5 2.5 3.5 6 6.5 8 10 12}

排序操作的结果不是一个大顶堆，而是一个小顶堆。尽管堆并不是全部有序的，但任何全部有序的序列都是堆。

如果用断言 greater() 来创建堆，会生成一个小顶堆，对它进行排序会生成一个降序序列。排序后的序列不是小顶堆。

std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers),std::greater<>());// {1.5 6 2.5 6.5 8 12 3.5 10}
std::sort_heap(std::begin(numbers), std::end(numbers),std::greater<>());//{12 10 8 6.5 6 3.5 2.5 1.5}

#include <iostream>                              
#include <iomanip>                              
#include <algorithm>                            
#include <string>                               
#include <deque>                        
using std::string;

void show(const std::deque<string>& words, size_t count = 5)
{
    if(words.empty()) return;                    
 
    auto max_len = std::max_element(std::begin(words), std::end(words),
                                  [](const string& s1, const string& s2)
                                  {return s1.size() < s2.size(); })->size();
    size_t n {count};
    for(const auto& word : words)
    {
        std::cout << std::setw(max_len + 1) << word << " ";
        if(--n) continue;
        std::cout << std::endl;
        n = count;
    }
    std::cout << std::endl;
}
int main()
{
    std::deque<string> words;
    std::string word;
    std::cout << "Enter words separated by spaces, enter Ctrl+Z on a separate line to end:\n";
    while (true)
    {
        if ((std::cin >> word).eof())
        {
            std::cin.clear();
            break;
        }
        words.push_back(word);
    }
    std::cout << "The words in the list are:" << std::endl;
    show(words);
    std::make_heap(std::begin(words), std::end(words));
    std::cout << "\nAfter making a heap, the words in the list are:" << std::endl;
    show(words);
    std::cout << "\nYou entered " << words.size() << " words. Enter some more:" << std::endl;
    while (true)
    {
        if ((std::cin >> word).eof())
        {
            std::cin.clear();
            break;
        }
        words.push_back(word);
        std::push_heap(std::begin(words), std::end(words));
    }
    std::cout << "\nThe words in the list are now:" << std::endl;
    show(words);
}

结果显示：