堆

今天做题时，看到这么一句话，最大/小堆的插入时间复杂度为O(logN)。但是为什么时O(logN)书中并没有解释。因此重温一下堆的定义和各种操作。

定义

堆是一个完全二叉树，每个节点都满足其值大(小)于左右子节点的值。即从根节点到任意子节点的路径都是有序序列。

//假设堆中的数据为int类型
typedef struct Heap *maxHeap;
struct Heap{
    int    *Data;  //存储堆数据的数组
    int    size;  //堆当前大小
    int    Cap;  //堆的最大容量
    Heap(int x): Data(nullptr), size(0), Cap(x) {}
}; 

堆的建立

Heap  CreateHeap(int MaxSize)
{
    Heap  H = new Heap(MaxSize);
    H->Data[0] = MAXDATA;   //定义一个哨兵,从Data[1]开始作为树的节点
    return H;
}

堆的插入

bool Insert(Heap H, int x)
{
    if(H->size>=H->Cap)
        return false;
    i = ++H->size;  //H->size为堆的最后一个位置，i指向size+1
    for(;H->Data[i/2]<x;i/=2)  //对于完全二叉树而言，叶节点/2 == 根节点
    {
        H->Data[i] = H->Data[i/2];  //当根节点小于插入的数值时，将根节点挪下来
    }
    H->Data[i] = x;
    return true;
}

由于从下至上走父节点来遍历，每次i都取其1/2，因此时间复杂度为O(logN)。