#ifndef priority_queue_h_
#define priority_queue_h_
#include <iostream>
#include <vector>
#include <cassert>
template <class T>
class priority_queue {
private:
std::vector<T> m_heap;
public:
priority_queue() {}
priority_queue(std::vector<T> const& values)
{
m_heap = values;
for (int i = 0; i < m_heap.size(); i++){
percolate_down(i);
for (int j = i; j < m_heap.size(); j++){
percolate_down(j);
}
}
}
const T& top() const
{
assert(!m_heap.empty());
return m_heap[0];
}
void push(const T& entry)
{
if (m_heap.size() == 0){
m_heap.push_back(entry);
return;
}
m_heap.push_back(entry);
percolate_up(m_heap.size() - 1);
}
void pop()
{
T val = m_heap[m_heap.size() - 1];
m_heap.pop_back();
m_heap[0] = val;
percolate_down(0);
}
void percolate_up(int i){
while (i > 0){
if (m_heap[i] < m_heap[(i - 1) / 2]){
swap((i - 1) / 2, i);
i = (i - 1) / 2;
}
else{
break;
}
}
}
void percolate_down(int i){
while ((2 * i + 1) < m_heap.size()){
int child;
if (2 * i + 2 < m_heap.size() && m_heap[2 * i + 2] < m_heap[2 * i + 1]){
child = 2 * i + 2;
}
else{
child = 2 * i + 1;
}
if (m_heap[child] < m_heap[i]){
swap(i, child);
i = child;
std::cout << "\n";
}
else{
break;
}
}
}
int size() { return m_heap.size(); }
bool empty() { return m_heap.empty(); }
// The following three functions are used for debugging.
// Check to see that internally the heap property is realized.
bool check_heap()
{
return this->check_heap(this->m_heap);
}
void swap(int i, int j){
T val = m_heap[j];
m_heap[j] = m_heap[i];
m_heap[i] = val;
}
// Check an external vector to see that the heap property is realized.
bool check_heap(const std::vector<T>& heap)
{
if (heap.size() == 0){
return true;
}
for (int i = 0; i < heap.size() / 2; i++){
if (heap[i] > heap[2 * i + 1] || heap[i] > heap[2 * i + 2]){
return false;
}
}
return true;
}
// A utility to print the contents of the heap. Use it for debugging.
void print_heap(std::ostream & ostr)
{
for (unsigned int i = 0; i<m_heap.size(); ++i)
ostr << i << ": " << m_heap[i] << std::endl;
}
};
template <class T>
void heap_sort(std::vector<T> & v)
{
//v_ = std::vector<T>(v);
priority_queue<T> pq_v(v);
for (int i = 0; i < v.size(); i++){
T temp = pq_v.top();
v[i] = temp;
pq_v.pop();
}
}
#endif