Difference between priority queue and a heap

Question

It seems that a priority queue is just a heap with normal queue operations like insert, delete, top, etc. Is this the correct way to interpret a priority queue? I know you can build priority queues in different ways but if I were to build a priority queue from a heap is it necessary to create a priority queue class and give instructions for building a heap and the queue operations or is it not really necessary to build the class?

What I mean is if I have a function to build a heap and functions to do operations like insert and delete, do I need to put all these functions in a class or can I just use the instructions by calling them in main.

I guess my question is whether having a collection of functions is equivalent to storing them in some class and using them through a class or just using the functions themselves.

What I have below is all the methods for a priority queue implementation. Is this sufficient to call it an implementation or do I need to put it in a designated priority queue class?

#ifndef MAX_PRIORITYQ_H
#define MAX_PRIORITYQ_H
#include <iostream>
#include <deque>
#include "print.h"
#include "random.h"

int parent(int i)
{
    return (i - 1) / 2;
}

int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}

int right(int i)
{
    if(i == 0)
        return 2;
    else
        return 2*i + 1;
}

void max_heapify(std::deque<int> &A, int i, int heapsize)
{
    int largest;
    int l = left(i);
    int r = right(i);
    if(l <= heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;
    if(r <= heapsize && A[r] > A[largest])
        largest = r;
    if(largest != i) {
        exchange(A, i, largest);
        max_heapify(A, largest, heapsize);
        //int j = max_heapify(A, largest, heapsize);
        //return j;
    }
    //return i;
}

void build_max_heap(std::deque<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        max_heapify(A, i, heapsize);
}

int heap_maximum(std::deque<int> &A)
{
    return A[0];
}

int heap_extract_max(std::deque<int> &A, int heapsize)
{
    if(heapsize < 0)
        throw std::out_of_range("heap underflow");
    int max = A.front();
    //std::cout << "heapsize : " << heapsize << std::endl;
    A[0] = A[--heapsize];
    A.pop_back();
    max_heapify(A, 0, heapsize);
    //int i = max_heapify(A, 0, heapsize);
    //A.erase(A.begin() + i);
    return max;
}

void heap_increase_key(std::deque<int> &A, int i, int key)
{
    if(key < A[i])
        std::cerr << "New key is smaller than current key" << std::endl;
    else {
        A[i] = key;
        while(i > 1 && A[parent(i)] < A[i]) {
            exchange(A, i, parent(i));
            i = parent(i);
        }
    }
}

void max_heap_insert(std::deque<int> &A, int key)
{
    int heapsize =  A.size();
    A[heapsize] = std::numeric_limits<int>::min();
    heap_increase_key(A, heapsize, key);
}

Answer 1

A priority queue is an abstract datatype. It is a shorthand way of describing a particular interface and behavior, and says nothing about the underlying implementation.

A heap is a data structure. It is a name for a particular way of storing data that makes certain operations very efficient.

It just so happens that a heap is a very good data structure to implement a priority queue, because the operations which are made efficient by the heap data strucure are the operations that the priority queue interface needs.

Answer 2

Having a class with exactly the interface you need (just insert and pop-max?) has its advantages.

• You can exchange the implementation (list instead of heap, for example) later.
• Someone reading the code that uses the queue doesn't need to understand the more difficult interface of the heap data structure.

I guess my question is whether having a collection of functions is equivalent to storing them in some class and using them through a class or just using the functions themselves.

It's mostly equivalent if you just think in terms of "how does my program behave". But it's not equivalent in terms of "how easy is my program to understand by a human reader"

Answer 3

The term priority queue refers to the general data structure useful to order priorities of its element. There are multiple ways to achieve that, e.g., various ordered tree structures (e.g., a splay tree works reasonably well) as well as various heaps, e.g., d-heaps or Fibonacci heaps. Conceptually, a heap is a tree structure where the weight of every node is not less than the weight of any node in the subtree routed at that node.