c++ - 最低优先级队列模板

Question

我正在制作最小优先级队列。我们提供了一个模板来使用它已经产生了一些问题。这是两个代码。

这是头文件。

#ifndef _PRIORITY_QUEUE_
#define _PRIORITY_QUEUE_
template <typename _T> struct element
{
    typedef _T data_type ;
    element () {}
    element (int _k, const _T & _e) : m_key (_k), m_element (_e) {}
    int m_key ;
    data_type  m_element ;
} ;
/*
 * compare keys of _e1 and _e2 
 */
template <typename _T> bool operator < (const element<_T> & _e1, const element<_T> & _e2)
{
    return _e1.m_key < _e2.m_key ;
}

template <typename _T> std::ostream & operator << (std::ostream & os, const element<_T> & _e)
{
    std::cout<<'['<<_e.m_key<<','<<_e.m_element<<']'<<std::endl; 
    return os ;
}


/**
 * Linear data structure implementation
 * _E is the element type
 */
template <typename _E>
class linear_heap 
{
public :
    typedef _E element_type ;
    typedef typename _E::data_type data_type; 

    linear_heap (int _s = 100) 
    {
        allocate_memory(_s);
        this->m_size = 0; 
    }

    unsigned size () const {return this->m_size ; }
    element_type & get_min () throw (const char *) 
    {
        if (true == is_empty()) throw ("Empty heap");
        return m_array[0] ;
    } ;

    void insert_element (const element_type & _e) 
    { 
        // implement 
    }
    void delete_min () throw (const char * )
    {
        if (true == is_empty()) throw ("Empty heap"); 
        // implement

    }
public :

    void update_element (element_type & _e, int _k)
    {
        // implement 
    }
    void build_heap () 
    {
        // implement
    } 
    void remove_element (element_type & _e)
    {
        // implement
    }

    bool is_empty () 
    {
        return (0 == m_size ); 
    }
    void allocate_memory (unsigned _s)
    {
        this->m_capacity = _s; 
        this->m_array.resize (this->m_capacity);
    }

protected :
    unsigned m_capacity  ; // The capacity of m_array 
    unsigned m_size ; // The number of current elements

    // implement
    // choose one of the following data structure. 
    std::vector<element_type> m_array ; // Storage of elements
//  std::list<element_type> m_array ; // Storage of elements

} ;


/**
 * Binary heap implementation 
 * _E is the element type
 */
template <typename _E>
class binary_heap 
{
public :
    typedef _E element_type ;
    typedef typename _E::data_type data_type; 

    binary_heap (int _s = 100) 
    {
        allocate_memory(_s); 
        this->m_size = 0; 
    }

    unsigned size () const {return this->m_size ; }
    element_type & get_min () throw (const char *) 
    {
        if (true == is_empty()) throw ("Empty heap");
        return m_array[0] ;
    } ;

    element_type & operator [] (unsigned id)
    {
        return m_array[id] ;
    }
    void insert_element (const element_type & _e) 
    { 
        // implement 
    }
    void delete_min () throw (const char * )
    {
        if (true == is_empty()) throw ("Empty heap"); 
        // implement

    }
public :

    void update_element (element_type & _e, int _k)
    {
        // implement 
    }
    void build_heap () 
    {
        // implement
    } 
    void remove_element (element_type & _e)
    {
        // implement
    }

    bool is_empty () 
    {
        return (0 == m_size ); 
    }
    void allocate_memory (unsigned _s)
    {
        this->m_capacity = _s; 
        this->m_array.resize (this->m_size);
    }


protected :
    unsigned m_capacity  ; // The capacity of m_array 
    unsigned m_size ; // The number of current elements
    std::vector<element_type> m_array ; // Storage of elements


} ;

/**
 * _H is the heap type. Could be array, list or binary heap. 
 *
 */
template <typename _H> class priority_queue  
{
public :
    typedef typename _H::element_type element_type ; 
    typedef typename _H::data_type   data_type ; 
    typedef _H heap_type ; 


    void insert (int _key, const data_type & _value)
    {
        m_heap.insert_element (element_type (_key, _value));
    }

    element_type & min ()
    {
        return m_heap.get_min();
    }

    element_type & get_loc (unsigned id)
    {
        return m_heap[id] ;
    }

    void createPriorityQueue () 
    {
        m_heap.build_heap (); 
    }

    void decreaseKey (element_type & _e, int _k)
    {
        m_heap.update_element (_e, _k) ;
    }

    void remove (element_type & _e)
    {
        m_heap.remove_element(_e) ;
    }
    unsigned size () const 
    {
        return m_heap.size(); 
    }
    bool isEmpty() 
    {
        return m_heap.is_empty(); 
    }
protected :
    heap_type m_heap ;
} ;


template <typename _H> std::istream & operator >> (std::istream & is, priority_queue <_H> & _p)
{
    typedef typename _H::element_type element_type ; 
    typedef typename _H::data_type   data_type ; 

    int key ;
    data_type value ;
    while (std::cin>>key>>value) 
    {
        _p.insert (key, value) ; 
    }
    return is ;
}

#endif

这是主文件。

#include <vector> 
#include <list>
#include <string>
#include <iostream>


#include "priority_queue.h"

int main()
{

    try
    {
        priority_queue<linear_heap<element<std::string> > > string_linear_heap ; 

        // create the binary heap . 
        priority_queue<binary_heap<element<std::string> > > string_binary_heap ; 
        std::cin>>string_binary_heap ;
        string_binary_heap.createPriorityQueue() ;

        // Decrease the key of the first element by 2. 
        // You may output the cost of decreaseKey here. 
        string_binary_heap.decreaseKey (string_binary_heap.get_loc(0), string_binary_heap.get_loc(0).m_key - 2);

        // Try to pop up elements in order w.r.t. their keys. 
        while (!string_binary_heap.isEmpty())
        {
            element <std::string> & loc = string_binary_heap.min() ;
            std::cout<<loc<<std::endl;
            // You may output the cost of remove here. 
            string_binary_heap.remove(loc); 
        }
    }

    catch (const char * msg)
    {
        std::cerr<<"  [EXCEPTION] "<<msg<<std::endl;
    }
    return 0;
}

当他们将其放入线性堆中时，这是否意味着 vector 以普通格式存储？通常，我的意思是将其描绘成一排分配了数据的正方形。另外，每当它说二叉堆时，它就将其存储为二叉树？

在实现功能时，您是否使用普通 vector 运算符(推回、删除等)？再次强调，这是作业。

Answer 1

vector 实现与其用法无关。您的 linear_heap 和 binary_heap 就 vector 中的存储而言是相同的。不同的是线性堆和二叉堆的插入/删除等算法。您需要以适合这些算法的方式使用 vector 容器(是的，您使用法线 vector 接口(interface))。例如，对于二进制堆，您可以在此处查看:Efficient Array Storage for Binary Tree