Template heap/priority-queue data structure with update-key operation

Question

I implemented the following priority-queue/heap with an update-key operation. The update key uses the map from STL, which still requires lg(n) time for lookup. However, replacing it with an unordered_map would require the client program to write hash and equal operations for each class, which is a problem in my case.

#ifndef IZ_HEAP_H
#define IZ_HEAP_H
#include <map>
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;
template <class T>
class IzHeap {
 class IzHeapItem {
 int key;
 T item;
 public:
 IzHeapItem(const int key, const T& item)
 : key(key), item(item) {}
 T getItem() const {return item;}
 int getKey() const {return key;}
 void updateKey(const int newKey) {key = newKey;}
 void updateItem(const T& newItem) {item = newItem;}
 IzHeapItem& operator=(const IzHeapItem& heapItem) {
 this->key = heapItem.getKey();
 this->item = heapItem.getItem();
 return *this;
 }
 };
 std::vector<IzHeapItem> heap;
 std::map<T, int> itemToHeapIndex;
 int leftChild(const int index) const {return index*2 + 1;}
 int rightChild(const int index) const {return index*2 + 2;}
 int parent(const int index) const {return (index - 1)/2;}
 void heapSwap(const int i, const int j) {
 /*
 IzHeapItem temp = heap[i];
 heap[i] = heap[j];
 heap[j] = temp;
 */
 std::swap(heap[i], heap[j]);
 itemToHeapIndex[getItem(i)] = i;
 itemToHeapIndex[getItem(j)] = j;
 }
 int getKey(const int index) const {return heap[index].getKey();}
 T getItem(const int index) const {return heap[index].getItem();}
protected:
 void shiftUp(const int index) {
 int largest{index}, p{parent(index)};
 if (p >= 0 && getKey(p) > getKey(index)) {
 largest = p;
 }
 if (largest != index) {
 heapSwap(largest, index);
 shiftUp(largest);
 }
 }
 void shiftDown(const int index) {
 int smallest{index}, lc{leftChild(index)}, rc{rightChild(index)};
 if (lc < heap.size() && getKey(lc) < getKey(smallest)) {
 smallest = lc;
 }
 if (rc < heap.size() && getKey(rc) < getKey(smallest)) {
 smallest = rc;
 }
 if (smallest != index) {
 heapSwap(smallest, index);
 shiftDown(smallest);
 }
 }
public:
 T extract() {
 assert(heap.size() > 0);
 heapSwap(0, heap.size() - 1);
 T item = heap.back().getItem();
 heap.pop_back();
 itemToHeapIndex.erase(item);
 shiftDown(0);
 return item;
 }
 T peak() {
 return heap[0];
 }
 bool empty() {
 return heap.size() == 0;
 }
 void insert(const T& item, const int key) {
 heap.push_back(IzHeapItem(key, item));
 itemToHeapIndex[item] = key;
 shiftUp(heap.size()-1);
 }
 void updateKey(const T& item, const int newKey) {
 assert(itemToHeapIndex.count(item) > 0);
 int index = itemToHeapIndex[item];
 int oldKey = getKey(index);
 heap[index].updateKey(newKey);
 if (newKey > oldKey) {
 shiftDown(index);
 }
 else {
 shiftUp(index);
 }
 }
 void heapify(const std::vector<T>& items, const std::vector<int>& keys) {
 assert(items.size() == keys.size());
 for (int i = 0; i < items.size(); ++i) {
 heap.push_back(IzHeapItem(keys[i], items[i]));
 itemToHeapIndex[items[i]] = i;
 }
 for (int i = heap.size()/2 - 1; i >=0; --i) {
 shiftDown(i);
 }
 }
 friend std::ostream& operator<<(std::ostream& out, const IzHeap<T>& heap) {
 for (auto& hi : heap.heap) {
 out << "(" << hi.getKey() << "->" << hi.getItem() << "), ";
 }
 return out;
 }
};
#endif

Please comment on any improvements that can be done on this code. This is my first time posting on code review, so please let me know of any norms I should follow.

Answer 1

1. peak() should be returning a const reference. same goes for getItem().

2. Extract() should not return anything. Having two functions to read the head just begs for someone to accidentally call Extract() when they meant peak().

3. Why is key forced to be an int? It could easily be a separate template parameter.

4. heap.push_back(IzHeapItem(keys[i], items[i])); should be heap.emplace_back(keys[i], items[i]); instead.

5. you should do a heap.reserve() at the top of heapify()

6. Heapifying a vector<> containing the same item twice would break this pretty badly. You should guard against this.

7. Unless you intend to call heapify() multiple times in a row, that should just be a constructor. Otherwise, I would rename that function addToHeap()

8. I prefer to avoid using the [] operator on maps in general unless I specifically want a "insert-or-replace" logic. There's a bunch of logic to handle creating a new instance, which assumes the value type of the map has a default constructor.

so:

itemToHeapIndex[items[i]] = i;

becomes

itemToHeapIndex.emplace(items[i], i);

and

assert(itemToHeapIndex.count(item) > 0);
int index = itemToHeapIndex[item];

becomes

auto found = itemToHeapIndex.find(item);
assert(found != itemToHeapIndex.end()); // Bonus! no additional lookup in debug
int index = found->second;

Super minor detail:

The peak() function name made me squint. Traditionally, peek() means "see the next value that will come out of the datastructure", which is what happens here. This is not really a problem you have to fix, more of an observation. I would personally have used top() and pop() to match established standards.

• Toby Speight: I'm not sure that peak() is a typo - isn't it the top (apex) of the heap?
• user128454: @TobySpeight I've never even considered it, thanks! I'll fix the review.
• Toby Speight: When I said "not sure", I meant it literally - I spent a minute or two trying to decide, before concluding that it really could be either!
• user128454: @TobySpeight That's enough for me to give OP the benefit of the doubt.