读书笔记: 最大堆 Max Heap

1
2
3
4
5
6
7
8
9
10

#include <stdio.h>
#define MAX_ELEMENTS 200
#define HEAP_FULL(n) (n == MAX_ELEMENTS -1)
#define HEAP_EMPTY(n) (!n)

typedef struct {
    int key;
}element;
element heap[MAX_ELEMENTS];
int n=0;

Insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//O(log2 n)
// insert item into a max heap of current size *n
void insert_max_heap(element item,int *n){
    int i;
    if(HEAP_FULL(*n)){
        exit(1);
    }
    i = ++(*n);
    while((i != 1) && (item.key > heap[i/2].key)){
        heap[i] = heap[i/2];
        i /=2;
    }
    heap[i]=item;
}

Delete

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//O(log2 n)
element delete_max_heap(int *n){
    //delete element with the highest key from the heap
    int parent, child;
    element item,temp;
    if(HEAP_EMPTY(*n)){
        exit(1);
    }
    // save value of the element with the highest key
    item = heap[1];
    //use last element in heap to adjust heap
    temp = heap[(*n)--];
    parent =1;
    child = 2;
    while(child <= *n){
        //find the larger child of the current parent
        if ((child < *n) && (heap[child].key < heap[child+1].key))
            child++;
        if(temp.key >= heap[child].key) break;
        //move to the next lower level 
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    return item;
}