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

Exercise 6.3-3

Show that there are at most nodes of height h in any n-element heap.

Answer

First we know that  nodes are leaves because of exercise 6.1-7. So being f(h) a function that gives us the number of nodes with height h of a heap of length n
we need to proof by induction that:

for the base case we have:

this holds because all the leaves have height 0. Let x be the number of nodes in a heap so that

so the number of leaves is

finally for inductive step we have:

Note: basically the idea is to "remove" each layer of leaves until we reach the ones with de desire heigth.

Exercise 6.1-3

Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.

Answer

The base case is trivial since is given by the definition of a max heap. Then we have that for any sub tree of size m so that the index of the root is i. The definition of a max heap can be applied recursively on the child's of i (2i and 2i+1) so by transitivity i most be the largest.

Exercise 6.1-2

Show that an n-element heap has

Answer

We can use the maximum and minimum from exercise 6.1-1

For the lower bound we have:

For the upper bound we have:

Exercise 6.1-1

What are the minimum and maximum numbers of elements in a heap of height h?

Answer

A heap of height h has the maximum number of elements when all h+1 floors are full. This is given by the summation:

On the other hand it has the minimum number of elements when the last floor has 1 node. This is given by:

so being n the number of nodes in a heap of height h