Loading...
Searching...
No Matches
heap.hh
#pragma once
/*
Copyright (c) 2003-2021 Tommi Junttila
Released under the GNU Lesser General Public License version 3.
This file is part of bliss.
bliss is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation, version 3 of the License.
bliss is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with bliss. If not, see <http://www.gnu.org/licenses/>.
*/
#include <vector>
#include <algorithm>
namespace bliss {
class Heap
{
std::vector<unsigned int> contents;
struct {
bool operator()(const unsigned int e1, const unsigned int e2) {return e1 > e2; }
} gt;
public:
bool is_empty() const {return contents.empty(); }
void clear() {contents.clear(); }
void insert(const unsigned int e) {
contents.push_back(e);
std::push_heap(contents.begin(), contents.end(), gt);
}
unsigned int smallest() const {return contents.front(); }
unsigned int remove() {
const unsigned int result = smallest();
std::pop_heap(contents.begin(),contents.end(), gt);
contents.pop_back();
return result;
}
size_t size() const {return contents.size(); }
};
} // namespace bliss
bliss::Heap
A min-heap of unsigned integers.
Definition heap.hh:32
bliss::Heap::clear
void clear()
Definition heap.hh:53
bliss::Heap::insert
void insert(const unsigned int e)
Definition heap.hh:60
bliss::Heap::size
size_t size() const
Definition heap.hh:86
bliss::Heap::smallest
unsigned int smallest() const
Definition heap.hh:69
bliss::Heap::remove
unsigned int remove()
Definition heap.hh:76
bliss::Heap::is_empty
bool is_empty() const
Definition heap.hh:47
bliss
Definition abstractgraph.cc:35