数据结构和算法分析--c语言描述堆

优先队列至少有两个数据模型 DeleteMin以及Insert

优先队列的实现是一个二叉堆，是一个数组，左子元素是 2n,又子元素是2n+1，树的高度是O(logN),

插入元素遵循上滤，弹出元素遵循下滤

上滤：

下滤：

 代码实现：

#include 
#include 
#include 
#include 

#define MinPQsize 10
#define MinData (-10000)
typedef int ElementType;
struct HeapStruct {
    int Capacity;
    int size;
    ElementType *Elements;
};



typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue H;

    if (MaxElements < MinPQsize) {
        exit(-1);
    }

    H = static_cast(malloc(sizeof(struct HeapStruct)));
    if (!H) {
        exit(-1);
    }

    H->Elements = static_cast(malloc(MaxElements + 1 * sizeof(ElementType)));
    bzero(H->Elements, MaxElements + 1 * sizeof(ElementType));
    H->size = 0;
    H->Capacity = MaxElements;
    H->Elements[0] = MinData;
    return H;
}

void Insert(ElementType X, PriorityQueue H) {
    int i;
    if (H->Capacity == H->size) {
        std::cout << "full" << std::endl;
        exit(-1);
    }

    for (i = ++ H->size; H->Elements[i >> 1] > X; i = i >> 1) {
        H->Elements[i] = H->Elements[i >> 1];
    }
    H->Elements[i] = X;
}

ElementType DeleteMin(PriorityQueue H) {
    int i, Child = 0;

    if (H->size == 0) {
        printf("H->size is emptyn");
        exit(-1);
        return H->Elements[0];
    }

    ElementType LastElement = H->Elements[H->size--];
    ElementType minElement = H->Elements[1];

    for (i = 1; (i << 1) <= H->size; i = Child) {
        Child = (i << 1);

        if (Child != H->size && H->Elements[Child + 1] < H->Elements[Child]) {
            Child++;
        }

        if (LastElement > H->Elements[Child]) {
            H->Elements[i] = H->Elements[Child];
        } else {
            break;
        }
    }
    H->Elements[i] = LastElement;
    return minElement;
}

void Print(PriorityQueue H) {
    std::cout << "debug" << std::endl;
    int i;
    for (i = 0; i <= H->size; i ++) {
        std::cout << H->Elements[i] << std::endl;
    }
}

void HeapIfy()

void BuildHeap(PriorityQueue H) {
    if (H->size == 0) {
        printf("queue is empty");
        return;
    }

    for (int i = n >> 1; i >= 1; i--) {

    }
}

int main() {
    PriorityQueue queue = Initialize(100);
    Insert(3, queue);
    Insert(5, queue);
    Insert(2, queue);
    Insert(1, queue);
    DeleteMin(queue);
    Print(queue);
    return 0;
}

不只有两个节点有多个节点

数组二叉堆合并，由于是一个数组，需要进行拷贝，这会导致出现O(N)的运算，所以我们需要使用指针来减少内存拷贝

坐式堆的性质：

零路径长：

X到一个没有两个儿子的最短路径长

左儿子的零路径长一定大于等于右路径长

左式堆的插入，是把单节点合并到另一个大二叉树上。

操作步骤：

1.将具有大根值的堆，与具有小根值堆的右子树进行合并

2.这时候堆并不是左式堆，但是右面的树是坐式堆，我们可以交换左右子树

#include 

struct TreeNode;

typedef struct TreeNode *PriorityQueue;
typedef int ElementType;

struct TreeNode {
    ElementType Element;
    PriorityQueue Left;
    PriorityQueue Right;
    int Npl; // 零路径长
};


PriorityQueue Initialize() {
    return nullptr;
}

ElementType FindMin(PriorityQueue H);

int IsEmpty(PriorityQueue H) {
    return H == nullptr;
}

void
SwapChildren( PriorityQueue H )
{
    PriorityQueue Tmp;

    Tmp = H->Left;
    H->Left = H->Right;
    H->Right = Tmp;
}

int IsEmpty(PriorityQueue H);

PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2);

static PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2) {
    if (H1->Left == nullptr) {
        H1->Left = H2;
    } else {
        H1->Right = Merge(H1->Right, H2) ;
        if (H1->Left->Npl < H1->Right->Npl) {
            SwapChildren(H1);
        }

        H1->Npl = H2->Right->Npl + 1;
    }
    return H1;
}

PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2) {
    if (H1 == nullptr) {
        return H2;
    }

    if (H2 == nullptr) {
        return H1;
    }

    if (H1->Element < H2->Element) {
        return Merge1(H1, H2);
    }
    return Merge1(H2, H1);
}

PriorityQueue Insert1(ElementType X, PriorityQueue H) {
    PriorityQueue SingleNode;

    SingleNode = static_cast(malloc(sizeof(struct TreeNode)));
    SingleNode->Element = X;
    SingleNode->Npl = 0;
    SingleNode->Left = SingleNode->Right = nullptr;
    H = Merge(SingleNode, H);
    return H;
}

PriorityQueue DeleteMin1(PriorityQueue H) {
    PriorityQueue LeftHeap, RightHeap;

    if (IsEmpty(H)) {
        printf("%s", "queue is emptyn");
        return H;
    }

    LeftHeap = H->Left;
    RightHeap = H->Right;
    free(H);
    return Merge(LeftHeap, RightHeap);
}

int main() {
    return 0;
}

三、二项树：

        typedef int ElementType;


        #ifndef _BinHeap_H
        #define _BinHeap_H

        struct HeapStruct;
        typedef struct HeapStruct *PriorityQueue;

        PriorityQueue Initialize( int MaxElements );
        void Destroy( PriorityQueue H );
        void MakeEmpty( PriorityQueue H );
        void Insert( ElementType X, PriorityQueue H );
        ElementType DeleteMin( PriorityQueue H );
        ElementType FindMin( PriorityQueue H );
        int IsEmpty( PriorityQueue H );
        int IsFull( PriorityQueue H );

        #endif

        #include "binheap.h"
        #include "fatal.h"
        #include 

        #define MinPQSize (10)
        #define MinData (-32767)

        struct HeapStruct
        {
            int Capacity;
            int Size;
            ElementType *Elements;
        };


        PriorityQueue
        Initialize( int MaxElements )
        {
            PriorityQueue H;

      if( MaxElements < MinPQSize )
          Error( "Priority queue size is too small" );

      H = malloc( sizeof( struct HeapStruct ) );
      if( H ==NULL )
          FatalError( "Out of space!!!" );

            
      H->Elements = malloc( ( MaxElements + 1 )
                                    * sizeof( ElementType ) );
      if( H->Elements == NULL )
          FatalError( "Out of space!!!" );

      H->Capacity = MaxElements;
      H->Size = 0;
      H->Elements[ 0 ] = MinData;

      return H;
        }


        void
        MakeEmpty( PriorityQueue H )
        {
            H->Size = 0;
        }


        

        void
        Insert( ElementType X, PriorityQueue H )
        {
            int i;

            if( IsFull( H ) )
            {
                Error( "Priority queue is full" );
                return;
            }

            for( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 )
                H->Elements[ i ] = H->Elements[ i / 2 ];
            H->Elements[ i ] = X;
        }



        ElementType
        DeleteMin( PriorityQueue H )
        {
            int i, Child;
            ElementType MinElement, LastElement;

      if( IsEmpty( H ) )
            {
          Error( "Priority queue is empty" );
          return H->Elements[ 0 ];
            }
      MinElement = H->Elements[ 1 ];
      LastElement = H->Elements[ H->Size-- ];

      for( i = 1; i * 2 <= H->Size; i = Child )
            {
                
          Child = i * 2;
          if( Child != H->Size && H->Elements[ Child + 1 ]
                                < H->Elements[ Child ] )
              Child++;

                
          if( LastElement > H->Elements[ Child ] )
              H->Elements[ i ] = H->Elements[ Child ];
                else
              break;
            }
      H->Elements[ i ] = LastElement;
      return MinElement;
        }


        ElementType
        FindMin( PriorityQueue H )
        {
            if( !IsEmpty( H ) )
                return H->Elements[ 1 ];
            Error( "Priority Queue is Empty" );
            return H->Elements[ 0 ];
        }

        int
        IsEmpty( PriorityQueue H )
        {
            return H->Size == 0;
        }

        int
        IsFull( PriorityQueue H )
        {
            return H->Size == H->Capacity;
        }

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

        #if 0

        for( i = N / 2; i > 0; i-- )
            PercolateDown( i );

        #endif