堆

最小堆插入算法时间复杂度为$O(logN)$

插入操作

/****************************************************************************************
 * Insert Operation
 ***************************************************************************************/
void min_heap_up_update(int key) {
    int p_node_index, new_node_index;
    
    /* set inserted node's init index */ 
    new_node_index = heap_size;
    /* get inserted node's father node's index and key */ 
    p_node_index = (new_node_index - 1 ) / 2;

    while (new_node_index > 0) {
        if (min_heap[p_node_index]<= key) {
           break; 
        } else {
            /* please note we do not swap key between father node and child 
             * node, we only assign father node's key to its child node's key */ 
            min_heap[new_node_index] = min_heap[p_node_index];
            new_node_index = p_node_index;
            p_node_index = (p_node_index - 1) / 2;
        }
    }
    /* at his point, we assign key to the inserted node */
    min_heap[new_node_index] = key;
}

void min_heap_insert(int key) {
    if (heap_size == MAX_SIZE) {
        printf("Min Heap is full...
"); 
        return;
    }
    
    min_heap[heap_size] = key; 
    min_heap_up_update(key);
    heap_size++; 
}

删除操作

/****************************************************************************************
 * Delete Operation
 ***************************************************************************************/
void min_heap_down_update(int position) {
    int c_node_index, cur_node_index, cur_node_val;
    
    cur_node_index = position;
    cur_node_val = min_heap[cur_node_index];
    c_node_index = 2 * cur_node_index + 1;
    
    while (c_node_index < heap_size) {
        /* if node has two children we choose the one with smaller key */
        if ((c_node_index < heap_size - 1) && (min_heap[c_node_index] > min_heap[c_node_index + 1])) 
            c_node_index = c_node_index + 1;

        if (cur_node_val <= min_heap[c_node_index]) { 
            break;
        } else {
            min_heap[cur_node_index] = min_heap[c_node_index];
            cur_node_index = c_node_index;
            c_node_index = 2 * c_node_index + 1;
        }
    }
    min_heap[cur_node_index] = cur_node_val; 
}

void min_heap_remove() {
    if (heap_size == 0) {
        printf("Min Heap is empty...
");
        return;
    }
    
    min_heap[0] = min_heap[heap_size - 1];  
    min_heap_down_update(0);
    heap_size--;
}

参考文章：https://segmentfault.com/a/1190000010850472

http://www.eecs.wsu.edu/~ananth/CptS223/Lectures/heaps.pdf

http://www.cnblogs.com/skywang12345/p/3610187.html

https://courses.edx.org/c4x/PekingX/04830050x/asset/Chap5_006Heap.pdf