标签: Data-Structures


摘要:本节包括二叉堆,左式堆,斜堆和二项队列几种数据结构

1. 二叉堆

优先队列至少支持下列2种操作:Insert,DeleteMIn(DeleteMax)。 优先队列的实现:

  1. 链表
  2. 二叉查找树
  3. 二叉堆的数组实现 堆是完全二叉树,它的堆序性

优先队列的声明:

#ifndef BINHEAP_BINHEAP_H
#define BINHEAP_BINHEAP_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Init(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(int X, PriorityQueue H);
int DeleteMin(PriorityQueue H);
int FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);
#endif //BINHEAP_BINHEAP_H
struct HeapStruct{
    int Capactiy;
    int Size;
    int *Elems;
};

初始化以及销毁:

PriorityQueue Init(int MaxElements){
    PriorityQueue H;
    H = malloc(sizeof(struct HeapStruct));
    H->Elems = malloc(sizeof(int)* (MaxElements + 1));
    H->Size = 0;
    H->Capactiy = MaxElements;
    H->Elems[0] = -9999;
    return H;
}

void Destroy(PriorityQueue H){
    free(H->Elems);
    free(H);
}

插入:

数组大小加1后。在从最后一个元素的父节点回溯到根节点的过程中,比较节点和要插入元素X的大小,如果X小,则将父节点的值转移到子节点中,直到遇到X比父节点值大的时候才退出循环,将X直接放入当前节点中。

void Insert(int X, PriorityQueue H){
    int i;
    if (IsFull(H)){
        return;
    }
    for(i = ++H->Size;H->Elems[i/2] > X; i /=2){
        H->Elems[i] = H->Elems[i/2];
    }
    H->Elems[i] = X;
    H->Elems[0] = H->Elems[1];
}

删除最小元:

最小堆的最小元是根,直接删除根。比较根的较小子节点和最后一个元素的大小,如果根的子节点小,则移动到父节点中,否则退出循环。

int DeleteMin(PriorityQueue H){
    int i,child;
    if (IsEmpty(H))
        return H->Elems[0];
    int X = H->Elems[H->Size--];
    int Min = H->Elems[1];

    for(i = 1; i * 2 <= H->Size; i = child){
        child = i * 2;
        if (child != H->Size && H->Elems[child + 1] < H->Elems[child]){
            child ++;
        }
        if (H->Elems[child] < X)
            H->Elems[i] = H->Elems[child];
        else
            break;
    }
    H->Elems[i] = X;
    return Min;
}

构建二叉堆-BUildHeap

以O(N)时间复杂度构建一个最小堆。

PriorityQueue BuildHeap(int *A, int N){
    PriorityQueue H;
    H = malloc(sizeof(struct HeapStruct));
    H->Size = N;
    H->Capactiy = N;
    H->Elems = malloc(sizeof(int) * (N + 1));
    int i;
    for( i = N/2; i > 0; i--){
        PercolateDown(i,A,N);
    }
    for (int j = 1; j <= N; ++j) {
        H->Elems[j] = A[j];
    }
    return H;
}

一个关键步骤即节点下滤(PercolateDewn) 主要是调整当前下标为index的节点的子树的堆序性。第一步是找到较小子节点,第二步比较父节点和子节点的大小,如果不满足堆序性,交换,重复直到满足堆序性

void PercolateDown(int index, int *A,int N){
    int child;
    int t;
    for( int i = index; i*2<=N; i = child){
        child = i * 2;
        if (child != N && A[child] > A[child + 1])
            child++;
        if(A[child] < A[i]){
            t = A[i];
            A[i] = A[child];
            A[child] = t;
        }
    }
}

2. 左式堆

左式堆建立在二叉树的基础上,不同于二叉堆, 左式堆不是完全二叉树,而且极不平衡。

性质: 零路径长(NPL):从X到一个没有左右儿子的节点的最短路径的长

  1. 任一节点的NPL比所有儿子节点的NPL的最小值多1
  2. 最小堆的特性:父节点属性值小于子节点属性值
  3. 堆中任一节点的左儿子的NPL >= 右儿子的NPL

左式堆节点结构

struct TreeNode{
    int Elem;
    PriorityQueue Left;
    PriorityQueue Right;
    int Npl;
};

左式堆的基本操作是合并,O(logN)

  1. 如果有一个堆是空树,直接返回另一个堆,否则根节点值大的堆和根节点值小的右子树递归合并,形成新的左式堆
  2. 合并后的新堆作为较小堆的右子树
  3. 如果堆根节点的NPL不符合左式堆的特性,交换左右子树
  4. 更新根节点的NPL

    PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2){
        if (H1 == NULL)
            return H2;
        if (H2 == NULL)
            return H1;
        if (H1->Elem < H2->Elem)
            return Merge1(H1,H2);
        else
            return Merge1(H2,H1);
    }
    
    
    PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2){
        if (H1->Left == NULL)// H1是单节点
            H1->Left = H2;
        else{
            H1->Right = Merge(H1->Right,H2);
            if (H1->Left->Npl < H1->Right->Npl)
                SwapChildren(H1);
            H1->Npl = H1->Right->Npl + 1;
        }
        return H1;
    }
    

插入操作可以看成单节点堆和另一个堆合并的情况,O(logN)

PriorityQueue Insert(int X, PriorityQueue H){
    Node P;
    P = malloc(sizeof(struct TreeNode));
    P->Elem = X;
    P->Left = P->Right = NULL;
    P->Npl = 0;
    H = Merge(P,H);
    return H;
}

删除最小数操作直接删除根节点,将左右子树合并形成新的左式堆,O(logN)

当全部删除后,会以从小到大的顺序排列元素,可以作为一种排序方法

PriorityQueue DeleteMin(PriorityQueue H){
    PriorityQueue LeftHeap,RightHeap;
    if (IsEmpty(H))
        return NULL;
    else{
        LeftHeap = H->Left;
        RightHeap = H->Right;
        free(H);
        return Merge(LeftHeap,RightHeap);
    }
}

其它操作(上滤,增加或降低关键字值)

void PercolateUp(int index, int *A){
    int parent;
    for (int i = index; i / 2>0 ; i /=2) {
        parent = i/2;
        if (A[parent] > A[index]){
            int t = A[parent];
            A[parent] = A[index];
            A[index] = t;
        }
        else
            break;
    }
}

void DecreaseKey(int index, int Incre, int *A){
    A[index] -=Incre;
    PercolateUp(index,A);
}
void IncreaseKey(int index, int Incre, int *A,int N){
    A[index] +=Incre;
    PercolateDown(index,A,N);
}

3. 斜堆

斜堆和左式堆类似于伸展树和AVL树,后者都需要在节点中保存额外的信息如高度和零路径

斜堆基本操作也是合并

  1. 如果一个是空堆,直接返回一个另一个斜堆
  2. 两个斜堆都非空,那么比较两个根节点,取较小堆的根节点作为新的根节点,较小堆根节点的右子树与较大堆递归合并
  3. 交换根的左右子树

与左式堆的合并稍有不同的是第3步

  1. 如果堆根节点的NPL不符合左式堆的特性,交换左右子树
  2. 更新根节点的NPL

4. 二项队列

二项队列是二项树的集合。二项树Bk由一个带有儿子B0,B1...Bk-1 的根组成

二项队列操作

二项队列结构

struct BinNode{
    int Elem;
    Position LeftChild;
    Position NextSibling;
};
struct Collection{
    int CurrentSize;
    BinTree TheTrees[MaxSize];
};

查找最小元

通过搜索所有的树根,O(logN)找到

合并

二项队列按照高度给二项树排序放在数组中。

合并相同大小的二项树例程

BinTree CombineTrees(BinTree T1,BinTree T2){
    if(T1->Elem > T2->Elem)
        return CombineTrees(T2,T1);
    T2->NextSibling = T1->LeftChild;
    T1->LeftChild = T2;
    return T1;
}

二项队列的合并类似于加法进位,有8种情况考虑,T1,T2以及Carry分别是二项队列H1和H2的树,上一次合并形成的树。对应的树合并后放入H1中,清空H2

BinQueue Merge(BinQueue H1, BinQueue H2){
    BinTree T1,T2,Carry = NULL;
    int i,j;
    H1->CurrentSize += H2->CurrentSize;
    for (int i = 0,j=1; j < H1->CurrentSize; ++i,j*=2) {
        T1 = H1->TheTrees[i];
        T2 = H2->TheTrees[i];
        switch (!!T1 + 2*!!T2 + 4*!!Carry){
            case 0://没有树
            case 1://只H1存在
                break;
            case 2://只H2存在
                H1->TheTrees[i] = H2;
                H2->TheTrees[i] = NULL;
                break;
            case 3://H1和H2存在
                Carry = CombineTrees(T1,T2);
                H1->TheTrees[i] = H2->TheTrees[i] = NULL;
                break;
            case 4://H1和H2不存在,Carry存在
                H1->TheTrees[i] = Carry;
                Carry = NULL;
                break;
            case 5://H1和Carray
                Carry = CombineTrees(T1,Carry);
                H1->TheTrees[i] = NULL;
                break;
            case 6://H2和Carry
                Carry = CombineTrees(T2,Carry);
                H2->TheTrees[i] = NULL;
                break;
            case 7://H1,H2和Carry都存在
                H1->TheTrees[i] = Carry;
                Carry = CombineTrees(T1,T2);
                H2->TheTrees[i] = NULL;
                break;
        }
    }
    return H1;
}

插入

插入是特殊情况的合并,创建单节点树,执行合并

BinQueue Insert(int Item, BinQueue H) {  
    BinTree NewNode;    //二项树B0  
    BinQueue OneItem;   //只有B0的二项队列  
    NewNode = malloc(sizeof(struct BinNode));  
    NewNode->Elem = Item;  
    NewNode->LeftChild = NewNode->NextSibling = NULL;  
    OneItem = Init(); 
    OneItem->CurrentSize = 1;  
    OneItem->TheTrees[0] = NewNode;  
    return Merge(H, OneItem);   //合并单节点的二项树构成的二项队列与H  
}  

删除最小元

首先确定最小根的下标。从原二项队列中删除当前二项树称H,二项树删除最小元后形成新的二项队列DeletedQueue,合并原二项队列和新的二项队列

int DeleteMin(BinQueue H){
    int i,j;
    int index;// array index;
    BinQueue DeletedQueue;
    Position DeletedTree, OldToot;
    int Min;
    Min = 9999;
    for (int k = 0; k < 10; ++k) {
        if(H->TheTrees[k] && H->TheTrees[k]->Elem < Min){
            index = k;
            Min = H->TheTrees[k]->Elem;
        }
    }
    DeletedTree = H->TheTrees[index];//指向当前最小根节点二项树
    OldToot = DeletedTree;
    DeletedTree = DeletedTree->LeftChild;
    free(OldToot);

    DeletedQueue = Init();
    DeletedQueue->CurrentSize = (1<<index) - 1;
    for(j = index - 1; j >= 0; j--){
        DeletedQueue->TheTrees[j] = DeletedTree;
        DeletedTree = DeletedTree->NextSibling;
        DeletedQueue->TheTrees[j]->NextSibling = NULL;
    }
    H->TheTrees[index] = NULL;
    H->CurrentSize -=DeletedQueue->CurrentSize + 1;
    Merge(H,DeletedQueue);
    return Min;
}

总结

优先队列有几种实现,标准的二叉堆,以及左式堆,斜堆和二项队列。在实现上不同,二叉堆利用了数组的特性,后三者通过指针。左式堆和斜堆类似于伸展树和AVL树,都是递归的完美实例,需要仔细咀嚼精华。