6-2 Analysis of d-ary heaps A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
a. How would you represent a d-ary heap in an array?
b. What is the height of a d-ary heap of n elements in terms of n and d?
c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
e. Give an efficient implementation of INCREASE-KEY(A,i,k), which flags an error if k is less than key at index i.
Answer
a) Being f a floor of the heap, the last index of a floor that is full is:
each index k that is in a floor i is bound by:
Using this bounds we can prove it for any element of floor i.
x being the index of a given element of floor i we have:
For the parent we have:
Proof;
b) For this question we can do the same we did for the proof of a binary heap height. Being h the height of the heap we can bound n in terms of h and d:
And so the height is:
d) Extract_max is Max_heapify plus constant time and Max_heapify for each recursive call needs to find the largest of d child, so the running time is:
c) and d)
Both are the running time of swim plus constant time. So their running time is:
d-ary heap implementation in C++(The root of the heap is zero instead of one):
#pragma once
#include <vector>
#include <iostream>
#include <algorithm>
template<class T, class Func= std::less<T>>
class DHeap
{
public:
DHeap();
DHeap(unsigned);
DHeap(unsigned,const Func&);
DHeap(const Func&);
T extractTop();
void insert(const T&);
void insert(T&&);
const T& top();
T changeKey(unsigned, T&&);
bool empty() const{ return vec.empty(); }
private:
std::vector<T> vec;
Func cmp;
int D;
void heapify(unsigned);
void swim(int);
unsigned maxIndex(unsigned, unsigned) const;
unsigned firstChild(unsigned) const;
int parent(int) const;
void ensureCapacity();
unsigned findMax(unsigned first, unsigned to) const;
template<typename U>
void genericInsert(U&&);
template< typename E>
friend std::ostream & operator<<(std::ostream &os, const DHeap<T,E>& p)
{
for (const T& d : p.vec)
os << d << ",";
return os;
}
};
template <typename T, typename F >
DHeap<T,F>::DHeap() : DHeap(4){}
template <typename T, typename F >
DHeap<T, F>::DHeap(unsigned d) : DHeap(d, F()){}
template <typename T, typename F >
DHeap<T, F>::DHeap(unsigned d, const F& func):D(d),cmp(func){}
template <typename T, typename F >
DHeap<T, F>::DHeap(const F& func) : DHeap(4, func){}
template <typename T, typename F >
T DHeap<T,F>::extractTop()
{
if (vec.size() < 1)
throw new std::underflow_error("underflow");
T max = std::move(vec[0]);
vec[0] = std::move(vec.back());
vec.pop_back();
heapify(0);
return max;
}
template<typename T, typename F>
const T& DHeap<T,F>::top()
{
return vec[0];
}
template<typename T, typename F>
template<typename U>
void DHeap<T,F>::genericInsert(U&& element)
{
ensureCapacity();
vec.push_back(std::forward<U>(element));
swim(vec.size() - 1);
}
template <typename T, typename F >
void DHeap<T,F>::insert(const T& element)
{
genericInsert(element);
}
template <typename T, typename F >
void DHeap<T,F>::insert(T&& element)
{
genericInsert(std::move(element));
}
template <typename T, typename F >
T DHeap<T,F>::changeKey(unsigned index, T&& element)
{
if (cmp(element, vec[index]))
throw new std::invalid_argument("invalid argument");
T old = std::move(vec[index]);
vec[index] = std::move(element);
swim(index);
return old;
}
template <typename T, typename F >
void DHeap<T,F>::heapify(unsigned index)
{
unsigned first = 0;
while ((first = firstChild(index)) < vec.size())
{
unsigned to = std::min(vec.size(), firstChild(index + 1));
unsigned largest = findMax(first, to);
if (!cmp(vec[index], vec[largest])) break;
using std::swap;
swap(vec[largest], vec[index]);
index = largest;
}
}
template<typename T, typename F>
unsigned DHeap<T,F>::maxIndex(unsigned a, unsigned b) const
{
return cmp(vec[a], vec[b])? b : a;
}
template <typename T, typename F >
void DHeap<T,F>::swim(int index)
{
using std::swap;
int p = 0;
while (index > 0 && cmp(vec[p = parent(index)], vec[index]))
{
swap(vec[p], vec[index]);
index = p;
}
}
template <typename T, typename F >
unsigned DHeap<T,F>::findMax(unsigned first, unsigned to) const
{
unsigned largest = first++;
while (first < to)
largest = maxIndex(largest, first++);
return largest;
}
template <typename T, typename F >
unsigned DHeap<T,F>::firstChild(unsigned index) const
{
return D* index + 1;
}
template <typename T, typename F >
int DHeap<T,F>::parent(int index) const
{
return (index - 1) / D;
}
template <typename T, typename F >
void DHeap<T,F>::ensureCapacity()
{
if (vec.size() == vec.capacity())
vec.reserve(3 * vec.size() / 2 + 1);
}
