Homework Assignment 2: Binary Heap with Element Modification

Introduction

In many algorithms, there is a need for the priority queue (heap) data structure; moreover, it is often useful to be able to modify the priority of an element in the heap. While the C++ standard defines std::priority_queue, this data structure does not support modification of elements. This means that algorithms requiring this functionality (such as Dijkstra’s algorithm) need to be implemented using various workarounds, which may lead to suboptimal (space) complexity.

Your task is to implement a binary heap data structure that supports modification (and deletion) of elements using handles. A handle is a unique identifier of an element in the heap, it refers to the same element even while the heap is being modified. This way, an element can be modified or deleted using a handle which was given for it when it was inserted.

Heap Type

template< typename T, std::strict_weak_order< T, T > Compare >
struct Heap;

The Heap type, parametrized by the type of elements and by the type that defines a comparator. The comparator is expected to be stateless and default constructible, so it does not need to be stored in the Heap. The ordering of the heap depends on the type supplied to Compare; with std::less< T > it creates a max-heap (this behaviour mirrors the one of std::priority_queue); see the end of the supplied file for some pre-defined heaps with comparators.

Unlike std::priority_queue, this type supports the in-place update of the stored values. For this reason it defines the Handle member type that represents a handle to an element of the heap. This handle needs to remain valid until the element is removed from the heap, or the heap is destructed. The handle can be used to update or remove the value from the heap, and to read the value. Note, however, that Heap does not define any iterators.

Implement Heap as the standard binary heap in an array (see e.g. https://en.wikipedia.org/wiki/Binary_heap), using std::vector as the underlying container (for the purpose of the complexity analysis, you may consider push_back to have constant complexity, although in fact it is only amortized constant). For each of the operations there is a complexity requirement that you have to meet. You are free to choose the type of the elements stored in the vector and you can use any additional data structures. Unless stated otherwise, the n in the complexity requirements refers to the size of the heap represented by *this.

Member Types

using value_type = T;
struct Handle;

Handle has to be default constructible, copy and move constructible, copy and move assignable, destructible, and support the equality comparison operators. Otherwise it is an opaque data structure (it defines no other public members).

A default-constructed handle has to be comparable to any valid handle (and should only be equal to other default-constructed handles).

Member Functions

Heap();

𝒪(1). Heap is default constructible in constant time.

Heap( const Heap& other );

𝒪(n) where n is the size of other. Heap is copy constructible. The copying does not affect other (and its handles) in any way; the handles from other shall not be used with *this.

Heap( Heap&& other );

𝒪(1). Heap is move constructible. After the move, no operations other than destruction or assignment shall be done with other and all handles for other shall now be valid handles for *this.

template< std::input_iterator I, std::sentinel_for< I > S >
Heap( I begin, S end ) {

𝒪(n) where n is the distance from begin to end. Heap can be created from an iterator range in linear time (ignoring the complexity of the iterator’s dereference and increment).

Note: For the purpose of this homework assignment, you may assume that the two types I and S are the same, which means that you do not need to use the new ranges part of std library here.

Heap( std::initializer_list< T > list );

𝒪(n) where n is the number of elements in list.

Heap& operator=( const Heap& other );

𝒪(n) where n is the size of other. Heap is copy assignable. The assignment does not affect other (and its handles) in any way; the handles from other shall not be used with *this.

Heap& operator=( Heap&& other );

𝒪(1). Heap is move assignable. After the move assignment, no operations other than destruction or assignment shall be done with other and all handles for other shall now be valid handles for *this.

~Heap();

𝒪(n). Invalidates all handles to *this.

void swap( Heap& other );

𝒪(1). Heap is swappable (the non-member swap function that calls this member function is provided for you in the supplied file). After the swap, all handles for *this shall be valid handles for other and vice versa.

const T& top() const;

𝒪(1). Get the top (e.g. maximal for max-heap) element of the heap.
Precondition: The heap is not empty.

Handle topHandle() const;

𝒪(1). Get handle to the top element of the heap.
Precondition: The heap is not empty.

void pop();

𝒪(log n). Remove the top element from the heap. This invalidates the handle to the removed element, handles to other elements shall remain valid.
Precondition: The heap is not empty.

Handle insert( const T& value );

𝒪(log n). Insert an element into the heap and return its handle. No handles are invalidated.

Handle insert( T&& value );

𝒪(log n). A version of insert that moves the element into the underlying container instead of copying it.

const T& get( const Handle& h ) const;

𝒪(1). Get the value of the element represented by the given handle.
Precondition: h is a valid handle for *this.

void update( const Handle& h, const T& value );

𝒪(log n). Update the value represented by the given handle (replace it by the new value).
Precondition: h has to be a valid handle for *this.

void update( const Handle& h, T&& value );

𝒪(log n). A version of update that uses move assignment instead of copy assignment to replace the value.

void erase( const Handle& h );

𝒪(log n). Erase the value represented by the given handle from the heap. Invalidates h, but does not invalidate handles to other elements.
Precondition: h has to be a valid handle for *this.

size_t size() const;

𝒪(1). Get the size (the number of elements) of the heap.

bool empty() const;

𝒪(1). Is the heap empty?

Namespace-level functions

template< typename T, typename Cmp, std::output_iterator< T > O >
void copySorted( Heap< T, Cmp > heap, O o );

𝒪(nlog n). Assigns the values of the heap in the sorted order (top first) to the output iterator. Ignore the complexity of the iterator’s increment and assignment.

Note that this function takes the heap by value; the reason for that is that the creation of a sorted range from a heap is a destructive operation. This way, the caller chooses whether they want their heap to be destroyed (with std::move) or copied (without std::move).

std::vector< T > toSortedVector( Heap< T, Cmp > heap );

𝒪(nlog n). Create a sorted vector form the given heap. See the above note.

Notes