Construct

Bottom Up Construction

void ConstructBottomUp(Bheap *B)
{
    int item, cur, tmp, min;
    char *str;
    while (scanf("%d", &item)) {
        if (B->size == MAX-1) {
            printf("Binary heap is full\n");
            break;
        }
        str = (char*)malloc(sizeof(char)*20);
        scanf("%s", str);
        B->size++;
        B->data[B->size] = str;
        B->priority[B->size] = item;
    }
    for (cur = B->size/2; cur >= 1; cur--) {    // start from B->size/2, because nodes with index larger than that do not have childs
        tmp = cur;
        while (B->size >= 2*tmp) {
            if (B->size == 2*tmp)
                min = 2*tmp;
            else
                min = B->priority[2*tmp] < B->priority[2*tmp+1] ? 2*tmp: 2*tmp+1;
 
            if (B->priority[tmp] > B->priority[min]) {
                Swap(B, tmp, min);
                tmp = min;
            }
            else
                break;
        }
    }
}

Time Complexity

(n/2)*1 + (n/4)*2 + (n/8)*3 +… + 1*logn = n * SUM(i/2i)i=1~logn = O(n)

Reference

http://en.wikipedia.org/wiki/List_of_mathematical_series

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License