heap.h

Go to the documentation of this file.

/*
 * This file is part of the alglib project.
 *
 * (c) Divyanshu Kakwani <divkakwani@gmail.com>
 *
 * For the full copyright and license information, please view the LICENSE file
 * that was distributed with this source code.
 */

#ifndef _HEAP_H
#define _HEAP_H

#include <boost/concept_check.hpp>
#include <functional>

namespace alglib {
namespace heap {

template<typename elt_t, typename key_t>
class min_heap {
    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<elt_t>));
    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<key_t>));

 public:
    virtual void insert(const elt_t& elt, const key_t& key) = 0;

    /* get the root */
    virtual const elt_t& get_min_elt() const = 0;
    virtual const key_t& get_min_key() const = 0;

    /* remove the root */
    virtual void delete_min() = 0;
    virtual void replace(const elt_t& elt, const key_t& key) = 0;

    /* Inspection */
    virtual int size() const = 0;
    virtual bool empty() const = 0;

    /* Internal modification */
    virtual void update_key(const elt_t& elt, const key_t& key) = 0;


    /* return a new heap that is the merger of the heap h and *this. */
    // min_heap<elt_t, Compare> merge_heaps(const min_heap<elt_t, Compare>& h);
};

}  // end heap namespace
}  // end alglib namespace


#endif // _HEAP_H