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?

CodePudding user response：

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

CodePudding user response：

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
}