0

The function int IsOnMinLevel(Heap H, int i), returns if the node of index i is on a min level (even level), in constant time

functions provided:

typedef struct heap
{
    int *array;
    int count;  
    int capacity;   
} *Heap;

Heap CreateHeap(int capacity)
{
    Heap h=(Heap) malloc(sizeof(struct heap));
    h->count=0;
    h->capacity=capacity;
    h->array=(int *)malloc(sizeof(int)*h->capacity);
    if(! h->array) return NULL;
    return h;
}
int Parent(Heap h, int i)
{
    if(i<=0 || i>=h->count)     
        return -1;
    return ((i-1)/2);
}
int LeftChild(Heap h, int i)
{
    int left = 2*i+1;
    if(left>=h->count) return -1;
    return left;
}
int RightChild(Heap h, int i)
{
    int right = 2*i+2;
    if(right>=h->count) 
        return -1;
    return right;
}
void ResizeHeap(Heap *h)
{
    int i;
    int *array_old = (*h)->array;
    (*h)->array=(int *)malloc(sizeof(int)*(*h)->capacity*2);    
 
    for(i=0; i<(*h)->capacity; i++) 
        (*h)->array[i]=array_old[i];    
    (*h)->capacity *=2;
    free(array_old);
}

How do I get level from index? And is there a relation between level and index in a complete binary tree?

Dancchi
  • 52
  • 6
  • 1
    Assuming the heap uses 0-based indexing, and that the root is on level 1, then given index `i`, the level is `floor(log2(i+1)) + 1` – user3386109 Nov 21 '22 at 10:26
  • 1
    @user3386109 shouldn't it be ```floor(log2(i+1))``` instead of ```floor(log2(i+1)) + 1```? – Dancchi Nov 21 '22 at 11:41
  • The implementation of `log` (or an integer variant such as `ilog2` - floor of log to the base 2) is generally bounded such that it does not depend (much) on the argument, so can be considered to be O(1). – Ian Abbott Nov 21 '22 at 11:41
  • @IanAbbott but since it's ```floor(log2(i+1))```, then ```index 0 = 1 | index 1 = 2 | index 2 = 2``` and so on, and it seems that the level numbering starts from ```level 1``` not ```level 0``` – Dancchi Nov 21 '22 at 11:57
  • @Dancchi Yes, you are correct. I shall delete my misleasing comment. – Ian Abbott Nov 21 '22 at 12:25

2 Answers2

1

Here is the level of the first few nodes:

index: 0 1 2 3 4 5 6 7 8 ...
level: 0 1 1 2 2 2 2 3 3 ...

The pattern is pretty simple: a new level starts at index 2^k-1. So if a node has an index between 2^k-1 included and 2^(k+1)-1 excluded, then it is at level k.

You can derive a formula from this: for a node with index i, find k such that 2^k-1 <= i < 2^(k+1)-1.
Add 1: 2^k <= i+1 < 2^(k+1).
Take the log2: k <= log2(i+1) < k+1.
Since k and k+1 are consecutive integers, this is equivalent to floor(log2(i+1)) = k.

It turns out the function floor(log2(i)) when i is an integer can be very efficiently written, for example like this (taken from here):

int uint64_log2(uint64_t n)
{
    #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }
    int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;
    #undef S
}

With this, your function becomes:

int IsOnMinLevel(Heap H, int i)
{
    return uint64_log2(i+1) % 2 == 0;
}
Nelfeal
  • 12,593
  • 1
  • 20
  • 39
0

The answer Given by @user3386109:

Assuming the heap uses 0-based indexing, and that the root is on level 1, then given index i, the level is floor(log2(i+1)) + 1

The function is simply:

int IsOnMinLevel(Heap H, int i)
{
    return ((int)(floor(log2(i+1))) % 2) == 0; //cast to int since log2 gives double
}
Dancchi
  • 52
  • 6