Problem 6-2 Analisis of d-ary heaps

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