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);
}

Ophiuchus

No, that’s not quite right. Did you read the respective Wikipedia articles? – Fiberboard

Using a heap is one way to implement a priority queue. It is a popular and efficient way, but it isn't the only way, so you could have a priority queue which was implemented without a heap. – Embryologist

These are two different class of abstractions. Priority queue is a an abstract data type like a queue that holds priorities, so when you add to a queue element, it does not got to the very end of the queue, but to the place that 'fits'. The heap, in general is a block of memory used to store stuff. – Kp

@Grzegorz: The are (at least) two kinds of "heap". The "Memory Pool" thing you mention, and the heap datastructure. – Diaphysis

@Diaphysis Yep, unfortunately the term is overloaded. See the Wikipedia disambiguation page. The heap data structure vs. the heap aka the free store. – Chari

This question is now clearly answered on Wikipedia : en.wikipedia.org/wiki/Priority_queue – Maidy

Answer 1

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"

Diaphysis

Answer 2

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.

Jackson

Or one could say that "heap" is a family of data structures, having in common that they maintain the "heap property", but which do that in different ways giving somewhat different performance characteristics. – Salted

"and says nothing about the underlying implementation" ? if not explicitly defined in constructor it is implemented as std::vector, isn't it? – Adrianadriana

@computer: The C++ standard makes certain promises about the underlying implementation of the std::priority_queue class template, but I'm talking general computer science here, nothing specific to any language or library. – Jackson

following the same logic, can't we say that a heap is itself an abstract datatype and the concrete implementation of that is a binary tree data structure – Taka

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.

Oaten

Just to confirm, will it be correct to say that heaps are a type of priority queue? – Seadon

@AdityaPrakash Heaps can be used to implement a priority queue. There may be other uses although off-hand I can’t think of any which can’t be seen as a priority queue… – Blocky

Answer 4

The C++ Standard Template Library provides the make_heap, push_heap and pop_heap algorithms for heaps (usually implemented as binary heaps), which operate on arbitrary random access iterators. It treats the iterators as a reference to an array, and uses the array-to-heap conversion. It also provides the container adaptor priority_queue, which wraps these facilities in a container-like class. However, there is no standard support for the decrease/increase-key operation.

priority_queue referes to abstract data type defined entirely by the operations that may be performed on it. In C++ STL prioroty_queue is thus one of the sequence adapters - adaptors of basic containers (vector, list and deque are basic because they cannot be built from each other without loss of efficiency), defined in <queue> header (<bits/stl_queue.h> in my case actually). As can be seen from its definition, (as Bjarne Stroustrup says):

container adapter provides a restricted interface to a container. In particular, adapters do not provide iterators; they are intended to be used only through their specialized interfaces.

On my implementation prioroty_queue is described as

/**
   *  @brief  A standard container automatically sorting its contents.
   *
   *  @ingroup sequences
   *
   *  This is not a true container, but an @e adaptor.  It holds
   *  another container, and provides a wrapper interface to that
   *  container.  The wrapper is what enforces priority-based sorting 
   *  and %queue behavior.  Very few of the standard container/sequence
   *  interface requirements are met (e.g., iterators).
   *
   *  The second template parameter defines the type of the underlying
   *  sequence/container.  It defaults to std::vector, but it can be
   *  any type that supports @c front(), @c push_back, @c pop_back,
   *  and random-access iterators, such as std::deque or an
   *  appropriate user-defined type.
   *
   *  The third template parameter supplies the means of making
   *  priority comparisons.  It defaults to @c less<value_type> but
   *  can be anything defining a strict weak ordering.
   *
   *  Members not found in "normal" containers are @c container_type,
   *  which is a typedef for the second Sequence parameter, and @c
   *  push, @c pop, and @c top, which are standard %queue operations.
   *  @note No equality/comparison operators are provided for
   *  %priority_queue.
   *  @note Sorting of the elements takes place as they are added to,
   *  and removed from, the %priority_queue using the
   *  %priority_queue's member functions.  If you access the elements
   *  by other means, and change their data such that the sorting
   *  order would be different, the %priority_queue will not re-sort
   *  the elements for you.  (How could it know to do so?)

template:

  template<typename _Tp, typename _Sequence = vector<_Tp>,
       typename _Compare  = less<typename _Sequence::value_type> >
    class priority_queue
    {

In opposite to this, heap describes how its elements are being fetched and stored in memory. It is a (tree based) data structure, others are i.e array, hash table, struct, union, set..., that in addition satisfies heap property: all nodes are either [greater than or equal to] or [less than or equal to] each of its children, according to a comparison predicate defined for the heap.

So in my heap header I find no heap container, but rather a set of algorithms

  /**
   * @defgroup heap_algorithms Heap Algorithms
   * @ingroup sorting_algorithms
   */ 

like:

• __is_heap_until
• __is_heap
• __push_heap
• __adjust_heap
• __pop_heap
• make_heap
• sort_heap

all of them (excluding __is_heap, commented as "This function is an extension, not part of the C++ standard") described as

   *  @ingroup heap_algorithms
   *
   *  This operation... (what it  does)

Adrianadriana

Answer 5

A priority queue is an abstract data structure that can be implemented in many ways-unsorted array,sorted array,heap-. It is like an interface, it gives you the signature of heap:

class PriorityQueue {
   top() → element
   peek() → element
   insert(element, priority)
   remove(element)
   update(element, newPriority)
   size() → int
}

A heap is a concrete implementation of the priority queue using an array (it can conceptually be represented as a particular kind of binary tree) to hold elements and specific algorithms to enforce invariants. Invariants are internal properties that always hold true throughout the life of the data structure.

here is the performance comparison of priority queue implementions:

Artichoke

Answer 6

Not really. The "priority" in the name stems from a priority value for the entries in the queue, defining their ... of course: priority. There are many ways to implement such a PQ, however.

Deictic