Data Structure

//在实现单向链表时，删除第一个结点可能导致链表的位置变化了（可以采用复制第二个结点的数据域到第一个结点，再删除第二个结点的方式来变相删除第一个结点）。
//更方便的办法是在第一个结点前增加head结点，它的数据域没有含义。
//下面是含有head结点的实现。
#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
}Node;

/* 带头链表，头结点数据域没有含义。 */
Node *create()
{
    Node *head = malloc(sizeof(Node));
    if (head == NULL) {
        printf("error when malloc");
        return NULL;
    }
    head->next = NULL;
    return head;
}

/* 返回含keyData的结点，如果有多个则返回第一个，没找到则返回NULL */
Node *find(Node *head, int keyData)
{
    Node *node = head->next;
    while( node != NULL && node->data != keyData){
        node = node->next;
    }
    return node;
}

/* 在keyData结点后面插入一个结点，如果keyData结点不存在，则插入到表头。 */
void insert(Node *head, int keyData, int data)
{
    Node *newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("error when malloc");
        return;
    }
    newNode->data = data;

    Node *keyNode = find(head, keyData);
    if (keyNode == NULL) { //没找到就插入到表头。
        newNode->next = head->next;
        head->next = newNode;
    } else {
        newNode->next = keyNode->next;
        keyNode->next = newNode;
    }
}

/* 带头结点链表的反转 */
void reverse(Node *head)
{
    if (head == NULL) { return; }

    Node *pNode = head->next;
    Node *pPrev = NULL;
    while (pNode != NULL) {
        Node *pNext = pNode->next;
        head->next = pNode;

        pNode->next = pPrev;

        pPrev = pNode;
        pNode = pNext;
    }
}

void print(Node *head){
    Node *node = head->next;
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

/* 如果keyData在链表中有多个，则删除第1个；
   如果keyData不在链表中，则什么也不做。*/
void delete(Node *head, int keyData)
{
    Node *p1 = head;
    /* 先找到含有keyData结点的前一个结点，保存到p1中。 */
    while(p1->next != NULL && p1->next->data != keyData) {
        p1 = p1->next;
    }
    if (p1->next != NULL) { // 如果p1不是最后结点，即链表中存在keyData结点。
        Node *node = p1->next;
        p1->next = node->next;
        free(node);
    }
}

/* 删除整个链表（删除带表头结点的列表，一般指删除除头结点外的所有结点）；
   当提到销毁列表时，才指删除包括表头结点在内的所有结点。*/
void deleteList(Node *head)
{
    Node *p = head->next;
    head->next = NULL;
    while(p != NULL) {
        Node *tmp = p->next; //删掉当前结点前，备份下一个结点。
        free(p);
        p = tmp;
    }
}

int main()
{
    Node *head = create();
    insert(head, 1, 2); //结点1不存在，所以会在表头插入结点2
    insert(head, 2, 3); //在结点2后插入结点3
    insert(head, 3, 4);
    insert(head, 2, 8); //在结点2后插入结点8
    print(head); //会打印出：2 8 3 4 
}

//栈的数组实现（C++）。
//注：类中有指针成员，所以有浅拷贝和深拷贝的问题（但这里没考虑）。
#include<cstdlib>
using std::rand;

#include<iostream>
using std::cerr;
using std::cout;
using std::endl;

template<typename T>
class Stack
{
public:
    Stack(int MaxStackTop=10);
    ~Stack(){delete[] stack;}
    bool isEmpty()const{return -1==TopOfStack;}
    bool isFull()const{return TopOfStack== Capacity;}
    void Push(const T& value);
    T Top()const; //返回栈顶元素。
    void Pop(); //栈顶元素出栈。
private:
    T *stack; //堆栈元素的数组。
    int TopOfStack; //栈顶，数组下标，元素个数减1。
    int Capacity;
};

template<typename T>
Stack<T>::Stack(int MaxStackTop)
{
    Capacity = MaxStackTop;
    stack = new T[MaxStackTop];

    TopOfStack = -1; //不要初始化为0，因为前面约定为元素个数减1。
}

template<typename T>
void Stack<T>::Push(const T& value)
{
    if(!isFull())
        stack[++TopOfStack]= value;
    else
        cerr<<"Full Stack!";
}

template<typename T>
T Stack<T>::Top()const
{
    if(!isEmpty())
        return stack[TopOfStack];
    else {
        cerr<<"Empty Stack!";
        return 0;//为避免编译警告，栈为空，弹出元素时将返回0。
    }
}

template<typename T>
void Stack<T>::Pop()
{
    if(!isFull())
        TopOfStack--;
    else
        cerr<<"Empty Stack!";
}

//测试栈
int main()
{
    int N = 20;
    Stack<int> a(N);
    cout<<"元素依次入栈"<<endl;
    for(int i=0; i < N; i++) {
        int tmp = rand()%100;
        cout<<tmp<<" ";
        a.Push(tmp);
    }
    cout<<endl<<"元素依次出栈"<<endl;
    for(int i=0; i < N; i++) {
        cout<<a.Top()<<" ";
        a.Pop();
    }
    return 0;
}

#include <stdlib.h>
#include<stdio.h>

typedef int ElementType;

struct AvlNode
{
    ElementType Element;
    struct AvlNode *Left;
    struct AvlNode *Right;
    int      Height;
};

typedef struct AvlNode *AvlTree;

int Height( AvlTree P )
{
    if( P == NULL )
        return -1;
    else
        return P->Height;
}

int Max( int Lhs, int Rhs )
{
    return Lhs > Rhs ? Lhs : Rhs;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */
AvlTree SingleRotateWithLeft( AvlTree K2 )
{
    AvlTree K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    K2->Height = Max( Height( K2->Left ), Height( K2->Right ) ) + 1;
    K1->Height = Max( Height( K1->Left ), K2->Height ) + 1;

    return K1;  /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */
AvlTree SingleRotateWithRight( AvlTree K1 )
{
    AvlTree K2;

    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    K1->Height = Max( Height( K1->Left ), Height( K1->Right ) ) + 1;
    K2->Height = Max( Height( K2->Right ), K1->Height ) + 1;

    return K2;  /* New root */
}

/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
AvlTree DoubleRotateWithLeft( AvlTree K3 )
{
    /* Rotate between K1 and K2 */
    K3->Left = SingleRotateWithRight( K3->Left );

    /* Rotate between K3 and K2 */
    return SingleRotateWithLeft( K3 );
}

/* This function can be called only if K1 has a right */
/* child and K1's right child has a left child */
/* Do the right-left double rotation */
/* Update heights, then return new root */
AvlTree DoubleRotateWithRight( AvlTree K1 )
{
    /* Rotate between K3 and K2 */
    K1->Right = SingleRotateWithLeft( K1->Right );

    /* Rotate between K1 and K2 */
    return SingleRotateWithRight( K1 );
}

AvlTree Insert( ElementType X, AvlTree T )
{
    if( T == NULL ) {
        /* Create and return a one-node tree */
        T = malloc( sizeof( struct AvlNode ) );
        if( T == NULL )
            //FatalError( "Out of space!!!" );
            printf("Out of space!!!" );
        else {
            T->Element = X; T->Height = 0;
            T->Left = T->Right = NULL;
        }
    }
    else if( X < T->Element ) {
        T->Left = Insert( X, T->Left );
        if( Height( T->Left ) - Height( T->Right ) == 2 )
            if( X < T->Left->Element )
                T = SingleRotateWithLeft( T );
            else
                T = DoubleRotateWithLeft( T );
    }
    else if( X > T->Element ) {
        T->Right = Insert( X, T->Right );
        if( Height( T->Right ) - Height( T->Left ) == 2 )
            if( X > T->Right->Element )
                T = SingleRotateWithRight( T );
            else
                T = DoubleRotateWithRight( T );
    }
    /* Else X is in the tree already; we'll do nothing */

    T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
    return T;
}

/* This function can be called only if K3 has a left */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
AvlTree DoubleRotateWithLeft( AvlTree K3 )
{
    AvlTree K1, K2;
    K1 = K3->Left;
    K2 = K1->Right;
    K1->Right = K2->Left;
    K3->Left = K2->Right;
    K2->Left = K1;
    K2->Right = K3;
    K1->Height = Max( Height(K1->Left), Height(K1->Right) ) + 1;
    K3->Height = Max( Height(K3->Left), Height(K3->Right) ) + 1;
    K2->Height = Max( K1->Height, K3->Height ) + 1;
    return K2;
}

//refers to:http://www.link.cs.cmu.edu/link/ftp-site/splaying/top-down-splay.c
/*
  An implementation of top-down splaying
  D. Sleator <sleator@cs.cmu.edu>
  March 1992
*/
#include <stdlib.h>
#include <stdio.h>
int size;  /* number of nodes in the tree */
/* Not actually needed for any of the operations */

typedef struct tree_node Tree;
struct tree_node
{
    Tree * left, * right;
    int item;
};

//在splay的实现中，在最后重新组装前，N.left和N.right分别指着右树和左树的根。
//在for循环中，l,r并不是指着左树和右树根，它们分别指着左树的最大节点和右树的最小节点。
Tree * splay (int i, Tree * t)
{
    /* Simple top down splay, not requiring i to be in the tree t.  */
    Tree N, *l, *r, *y;
    if (t == NULL)
        return t;
    N.left = N.right = NULL;
    l = r = &N;
    for (;;) {
        if (i < t->item) {
            if (t->left == NULL) {
                break;
            }
            if (i < t->left->item) {   /*  zig-zig case  */
                y = t->left;                           /* rotate right */
                t->left = y->right;
                y->right = t;
                t = y;
                if (t->left == NULL) {
                    break;
                }
            }
            r->left = t;                               /* link right */
            r = t;
            t = t->left;
        } else if (i > t->item) {
            if (t->right == NULL) {
                break;
            }
            if (i > t->right->item) {   /*  zag-zag case  */
                y = t->right;                          /* rotate left */
                t->right = y->left;
                y->left = t;
                t = y;
                if (t->right == NULL) {
                    break;
                }
            }
            l->right = t;                              /* link left */
            l = t;
            t = t->right;
        } else {
            break;
        }
    }
    l->right = t->left;                                /* assemble */
    r->left = t->right;
    t->left = N.right;
    t->right = N.left;
    return t;
}


Tree * insert(int i, Tree * t)
{
    /* Insert i into the tree t, unless it's already there.    */
    /* Return a pointer to the resulting tree.                 */
    Tree * new;
    new = (Tree *) malloc (sizeof (Tree));
    if (new == NULL) {
        printf("Ran out of space\n");
        exit(1);
    }
    new->item = i;
    if (t == NULL) {
        new->left = new->right = NULL;
        size = 1;
        return new;
    }
    t = splay(i,t);
    if (i < t->item) {
        new->left = t->left;
        new->right = t;
        t->left = NULL;
        size ++;
        return new;
    } else if (i > t->item) {
        new->right = t->right;
        new->left = t;
        t->right = NULL;
        size++;
        return new;
    } else {
        /* We get here if it's already in the tree */
        free(new);
        return t;
    }
}
 
Tree * delete(int i, Tree * t)
{
    /* Deletes i from the tree if it's there.               */
    /* Return a pointer to the resulting tree.              */
    Tree * x;
    if (t==NULL) {
        return NULL;
    }
    t = splay(i,t);
    if (i == t->item) {               /* found it */
        if (t->left == NULL) {
            x = t->right;
        } else {
            x = splay(i, t->left);
            x->right = t->right;
        }
        size--;
        free(t);
        return x;
    }
    return t;                         /* It wasn't there */
}

int main(int argv, char *argc[])
{
    /* A sample use of these functions.  Start with the empty tree,         */
    /* insert some stuff into it, and then delete it                        */
    Tree * root;
    int i;
    root = NULL;              /* the empty tree */
    size = 0;
    for (i = 0; i < 1024; i++) {
        root = insert((541*i) & (1023), root);
    }
    printf("size = %d\n", size);
    for (i = 0; i < 1024; i++) {
        root = delete((541*i) & (1023), root);
    }
    printf("size = %d\n", size);
}

#include <stdlib.h>
#include <stdio.h>

struct AANode;
typedef struct AANode *Position;
typedef struct AANode *AATree;

struct AANode
{
    int Element;
    AATree      Left;
    AATree      Right;
    int         Level;
};

Position NullNode = NULL;  /* Needs more initialization */

AATree
Initialize( void )
{
    if( NullNode == NULL ) {
            NullNode = malloc( sizeof( struct AANode ) );
            if( NullNode == NULL )
                printf( "Out of space!!!" );
            NullNode->Left = NullNode->Right = NullNode;
            //上面这种使用哨兵节点的技巧可以简化程序，不用检测空节点；
            //这种技巧在实现红黑树时也常用。
            NullNode->Level = 0;
        }
    return NullNode;
}

static Position
SingleRotateWithLeft( Position K2 )
{
    Position K1;
    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;
    return K1;  /* New root */
}

static Position
SingleRotateWithRight( Position K1 )
{
    Position K2;
    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;
    return K2;  /* New root */
}

/* If T's left child is on the same level as T, */
/* perform a rotation */
AATree
Skew( AATree T )
{
    if( T->Left->Level == T->Level )
        T = SingleRotateWithLeft( T );
    return T;
}

/* If T's rightmost grandchild is on the same level, */
/* rotate right child up */
AATree
Split( AATree T )
{
    if( T->Right->Right->Level == T->Level ) { //有哨兵节点，不用担心为空
        T = SingleRotateWithRight( T );
        T->Level++;
    }
    return T;
}

AATree
Insert( int Item, AATree T )
{
    if( T == NullNode ) {
        /* Create and return a one-node tree */
        T = malloc( sizeof( struct AANode ) );
        if( T == NULL )
            printf( "Out of space!!!" );
        else {
            T->Element = Item;
            T->Level = 1;
            T->Left = T->Right = NullNode;
        }
    }
    else {
        if( Item < T->Element )
            T->Left = Insert( Item, T->Left );
        else if( Item > T->Element )
            T->Right = Insert( Item, T->Right );
        /* Otherwise it's a duplicate; do nothing */
    }

    T = Skew( T );
    T = Split( T );
    return T;
}

void Print(AATree T)
{
    if (T != NullNode) {
        Print(T->Left);
        printf("%d, %d\n", T->Element, T->Level);
        Print(T->Right);
    }
}

int main(int argv, char *argc[])
{
    NullNode = Initialize();
    AATree root = NullNode;
    int i;
    for (i = 0; i < 1024; i++) {
        root = Insert((541*i) & (1023), root);
    }
    Print(root);
}

//DeletePtr和LastPtr可看作全局的，它们最后分别指向期待被删除的节点和实际上被删除的节点（它们可能指向同一个节点）。
AATree
Remove( int Item, AATree T )
{
    static Position DeletePtr, LastPtr;

    if( T != NullNode ) {
        /* Step 1: Search down tree */
        /*         set LastPtr and DeletePtr */
        LastPtr = T;
        if( Item < T->Element )
            T->Left = Remove( Item, T->Left );
        else {
            DeletePtr = T;
            T->Right = Remove( Item, T->Right );
        }

        /* Step 2: At the bottom of the tree we remove it */
        /*         if it is present */
        if( T == LastPtr ) {
            if( DeletePtr != NullNode &&
                Item == DeletePtr->Element )
                {
                    DeletePtr->Element = T->Element;
                    DeletePtr = NullNode;
                    T = T->Right;
                    free( LastPtr );
                }
        }
        /* Step 3: On the way back, we are not at the bottom; */
        /*         we rebalance */
        else if( T->Left->Level < T->Level - 1 ||
                 T->Right->Level < T->Level - 1 ) {
            T->Level = T->Level – 1;
            if( T->Right->Level > T->Level )
                T->Right->Level = T->Level;
            T = Skew( T );
            T->Right = Skew( T->Right );
            T->Right->Right = Skew( T->Right->Right );
            T = Split( T );
            T->Right = Split( T->Right );
        }
    }
    return T;
}

#include <stdlib.h>
#include <stdio.h>

struct TreapNode;
typedef struct TreapNode *Position;
typedef struct TreapNode *Treap;
typedef int ElementType;

#define Infinity 32767

struct TreapNode
{
    ElementType Element;
    Treap       Left;
    Treap       Right;
    int         Priority;
};

Position NullNode = NULL;  /* Needs initialization */

Treap
Initialize( void )
{
    if( NullNode == NULL ) {
        NullNode = malloc( sizeof( struct TreapNode ) );
        if( NullNode == NULL )
            printf( "Out of space!!!" );
        NullNode->Left = NullNode->Right = NullNode;
        NullNode->Priority = Infinity;
    }
    return NullNode;
}

int
Random( void )
{
    return rand() % Infinity; //Use ANSI C random number generator for simplicity
}

static Position
SingleRotateWithLeft( Position K2 )
{
    Position K1;
    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;
    return K1;  /* New root */
}

static Position
SingleRotateWithRight( Position K1 )
{
    Position K2;
    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;
    return K2;  /* New root */
}

Treap
Insert( ElementType Item, Treap T )
{
    if( T == NullNode ) {
        /* Create and return a one-node tree */
        T = malloc( sizeof( struct TreapNode ) );
        if( T == NULL )
            printf( "Out of space!!!" );
        else {
            T->Element = Item;
            T->Priority = Random();   //新插入节点使用随机值作为Priority
            T->Left = T->Right = NullNode;
        }
    } else if( Item < T->Element ) {
        T->Left = Insert( Item, T->Left );
        if( T->Left->Priority < T->Priority )
            T = SingleRotateWithLeft( T );
    } else if( Item > T->Element ) {
        T->Right = Insert( Item, T->Right );
        if( T->Right->Priority < T->Priority )
            T = SingleRotateWithRight( T );
    }
    /* Otherwise it's a duplicate; do nothing */

    return T;
}

Treap
Remove( ElementType Item, Treap T )
{
    if( T != NullNode ) {
        if( Item < T->Element )
            T->Left = Remove( Item, T->Left );
        else if( Item > T->Element )
            T->Right = Remove( Item, T->Right );
        else {
            /* Match found */
            if( T->Left->Priority < T->Right->Priority )
                T = SingleRotateWithLeft( T );
            else
                T = SingleRotateWithRight( T );

            if( T != NullNode )    /* Continue on down */
                T = Remove( Item, T );
            else {
                /* At a leaf */
                free( T->Left );
                T->Left = NullNode;
            }
        }
    }
    return T;
}

Treap
MakeEmpty( Treap T )
{
    if( T != NullNode ) {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T );
    }
    return NullNode;
}

void
PrintTree( Treap T )
{
    if( T != NullNode ) {
        PrintTree( T->Left );
        printf( "%d ", T->Element );
        PrintTree( T->Right );
    }
}

int main(int argv, char *argc[])
{
    NullNode = Initialize();
    Treap root = NullNode;
    int i;
    for (i = 0; i < 1024; i++) {
        root = Insert((541*i) & (1023), root);
    }
    printf("\nPrint after Insert:\n");
    PrintTree(root);
    for (i = 0; i < 1024; i++) {
        root = Remove((541*i) & (1023), root);
    }
    printf("\nPrint after Remove:\n");
    PrintTree(root);
}

// skipNode.h (C++) node type used in skip lists
// node with a next and element field; element is a pair<const K, E>
// next is a 1D array of pointers

#ifndef skipNode_
#define skipNode_

using namespace std;

template <class K, class E>
struct skipNode
{
   typedef pair<const K, E> pairType;
   pairType element;
   skipNode<K,E> **next;   // 1D array of pointers

   skipNode(const pairType& thePair, int size)
            :element(thePair){next = new skipNode<K,E>* [size];}
};

#endif

// skipList.h (C++) skip list data structure, implements dictionary

#ifndef skipList_
#define skipList_

#include <iostream>
#include <math.h>
#include <stdlib.h> // rand() RAND_MAX
#include <sstream>
#include <string>
#include "skipNode.h"

using namespace std;

template<class K, class E>
class skipList
{
   public:
      skipList(K, int maxPairs = 10000, float prob = 0.5);
      ~skipList();

      bool empty() const {return dSize == 0;}
      int size() const {return dSize;}
      pair<const K, E>* find(const K&) const;
      void erase(const K&);
      void insert(const pair<const K, E>&);
      void output(ostream& out) const;

   protected:
      float cutOff;          // used to decide level number
      int level() const;     // generate a random level number
      int levels;            // max current nonempty chain
      int dSize;             // number of pairs in dictionary
      int maxLevel;          // max permissible chain level
      K tailKey;             // a large key
      skipNode<K,E>* search(const K&) const; // search saving last nodes seen
      skipNode<K,E>* headerNode;  // header node pointer
      skipNode<K,E>* tailNode;    // tail node pointer
      skipNode<K,E>** last;       // last[i] = last node seen on level i
};

template<class K, class E>
skipList<K,E>::skipList(K largeKey, int maxPairs, float prob)
{// Constructor for skip lists with keys smaller than largeKey and
 // size at most maxPairs. 0 < prob < 1.
   cutOff = prob * RAND_MAX;
   maxLevel = (int) ceil(logf((float) maxPairs) / logf(1/prob)) - 1;
   levels = 0;  // initial number of levels
   dSize = 0;
   tailKey = largeKey;

   // create header & tail nodes and last array
   pair<K,E> tailPair;
   tailPair.first = tailKey;
   headerNode = new skipNode<K,E> (tailPair, maxLevel + 1);
   tailNode = new skipNode<K,E> (tailPair, 0);
   last = new skipNode<K,E> *[maxLevel+1];

   // header points to tail at all levels as lists are empty
   for (int i = 0; i <= maxLevel; i++)
       headerNode->next[i] = tailNode;
}

template<class K, class E>
skipList<K,E>::~skipList()
{// Delete all nodes and array last.
   skipNode<K,E> *nextNode;

   // delete all nodes by following level 0 chain
   while (headerNode != tailNode) {
      nextNode = headerNode->next[0];
      delete headerNode;
      headerNode = nextNode;
   }
   delete tailNode;

   delete [] last;
}

template<class K, class E>
pair<const K,E>* skipList<K,E>::find(const K& theKey) const
{// Return pointer to matching pair.
 // Return NULL if no matching pair.
   if (theKey >= tailKey)
      return NULL;  // no matching pair possible

   // position beforeNode just before possible node with theKey
   skipNode<K,E>* beforeNode = headerNode;
   for (int i = levels; i >= 0; i--)          // go down levels
      // follow level i pointers
      while (beforeNode->next[i]->element.first < theKey)
         beforeNode = beforeNode->next[i];

   // check if next node has theKey
   if (beforeNode->next[0]->element.first == theKey)
      return &beforeNode->next[0]->element;

   return NULL;  // no matching pair
}

template<class K, class E>
int skipList<K,E>::level() const
{// Return a random level number <= maxLevel.
 // 注：可以简化随机level值的生成，根本不需要cutOff
   int lev = 0;
   while (rand() <= cutOff)
      lev++;
   return (lev <= maxLevel) ? lev : maxLevel;
}

template<class K, class E>
skipNode<K,E>* skipList<K,E>::search(const K& theKey) const
{// Search for theKey saving last nodes seen at each
 // level in the array last
 // Return node that might contain theKey.
   // position beforeNode just before possible node with theKey
   skipNode<K,E>* beforeNode = headerNode;
   for (int i = levels; i >= 0; i--) {
      while (beforeNode->next[i]->element.first < theKey)
         beforeNode = beforeNode->next[i];
      last[i] = beforeNode;  // last level i node seen
   }
   return beforeNode->next[0];
}

template<class K, class E>
void skipList<K,E>::insert(const pair<const K, E>& thePair)
{// Insert thePair into the dictionary. Overwrite existing
 // pair, if any, with same key.
   if (thePair.first >= tailKey) {// key too large
       // TODO: throw exception
       return;
   }

   // see if pair with theKey already present
   skipNode<K,E>* theNode = search(thePair.first);
   if (theNode->element.first == thePair.first) {
      // update theNode->element.second
      theNode->element.second = thePair.second;
      return;
   }

   // not present, determine level for new node
   int theLevel = level(); // level of new node
   // fix theLevel to be <= levels + 1
   if (theLevel > levels) {
      theLevel = ++levels;
      last[theLevel] = headerNode;
   }

   // get and insert new node just after theNode
   skipNode<K,E>* newNode = new skipNode<K,E>(thePair, theLevel + 1);
   for (int i = 0; i <= theLevel; i++)  {
      // insert into level i chain
      newNode->next[i] = last[i]->next[i];
      last[i]->next[i] = newNode;
   }

   dSize++;
   return;
}

template<class K, class E>
void skipList<K,E>::erase(const K& theKey)
{// Delete the pair, if any, whose key equals theKey.
   if (theKey >= tailKey) // too large
      return;

   // see if matching pair present
   skipNode<K,E>* theNode = search(theKey);
   if (theNode->element.first != theKey) // not present
      return;

   // delete node from skip list
   for (int i = 0; i <= levels &&
                   last[i]->next[i] == theNode; i++)
      last[i]->next[i] = theNode->next[i];

   // update levels
   while (levels > 0 && headerNode->next[levels] == tailNode)
       levels--;

   delete theNode;
   dSize--;
}

template<class K, class E>
void skipList<K,E>::output(ostream& out) const
{// Insert the dictionary pairs into the stream out.
   // follow level 0 chain
   for (skipNode<K,E>* currentNode = headerNode->next[0];
                       currentNode != tailNode;
                       currentNode = currentNode->next[0])
      out << currentNode->element.first << " "
          << currentNode->element.second << "  ";
}

// overload <<
template <class K, class E>
ostream& operator<<(ostream& out, const skipList<K,E>& x)
   {x.output(out); return out;}

#endif

// test skip list class
#include <iostream>
#include "skipList.h"

using namespace std;

int main()
{
   skipList<int, int> z(1000);
   pair<int, int> p;

   // test insert
   p.first = 2; p.second = 10;
   z.insert(p);
   p.first = 10; p.second = 50;
   z.insert(p);
   p.first = 6; p.second = 30;
   z.insert(p);
   p.first = 8; p.second = 40;
   z.insert(p);
   p.first = 1; p.second = 5;
   z.insert(p);
   p.first = 12; p.second = 60;
   z.insert(p);
   cout << "The dictionary is " << z << endl;
   cout << "Its size is " << z.size() << endl;

   // test find
   cout << "Element associated with 1 is " << z.find(1)->second << endl;
   cout << "Element associated with 6 is " << z.find(6)->second << endl;
   cout << "Element associated with 12 is " << z.find(12)->second << endl;

   // test erase
   z.erase(1);
   z.erase(2);
   z.erase(6);
   z.erase(12);
   cout << "Deleted 1, 2, 6, 12" << endl;
   cout << "The dictionary is " << z << endl;
   cout << "Its size is " << z.size() << endl;
}

/* This test code would output following:
The dictionary is 1 5  2 10  6 30  8 40  10 50  12 60 
Its size is 6
Element associated with 1 is 5
Element associated with 6 is 30
Element associated with 12 is 60
Deleted 1, 2, 6, 12
The dictionary is 8 40  10 50 
Its size is 2
*/

// BuildHeap
for (i = N/2; i > 0; i--)
    PercolateDown(i);       //PercolateDown是“下滤”操作，即DeleteMin中介绍的算法

#include <stdio.h>
#include <stdlib.h>

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

typedef int ElementType;
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

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

PriorityQueue
Initialize( int MaxElements )
{
    PriorityQueue H;
    if( MaxElements < MinPQSize )
        printf( "Priority queue size is too small" );

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

    /* Allocate the array plus one extra for sentinel */
    H->Elements = malloc( ( MaxElements + 1 ) * sizeof( ElementType ) );
    if( H->Elements == NULL )
        printf( "Out of space!!!" );

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

    return H;
}

/* H->Element[ 0 ] is a sentinel */
void
Insert( ElementType X, PriorityQueue H )
{
    int i;
    if( H->Size == H->Capacity ) {
        printf( "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( H->Size == 0 ) {
        printf( "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 ) {
        /* Find smaller child */
        Child = i * 2;
        if( Child != H->Size && H->Elements[ Child + 1 ]
                              < H->Elements[ Child ] )
            Child++;

        /* Percolate one level */
        if( LastElement > H->Elements[ Child ] )
            H->Elements[ i ] = H->Elements[ Child ];
        else
            break;
    }
    H->Elements[ i ] = LastElement;
    return MinElement;
}

int main()
{
    PriorityQueue PQ = Initialize(100);
    Insert(1, PQ);
    Insert(2, PQ);
    Insert(3, PQ);
    printf("size %d\n", PQ->Size);
    DeleteMin(PQ);
    DeleteMin(PQ);
    printf("size %d\n", PQ->Size);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef long ElementType;
#define Infinity (30000L)
#define MaxTrees (14)   /* Stores 2^14 -1 items */
#define Capacity (16383) /* 16383 = 2^14 -1 */

struct BinNode
{
    ElementType Element;
    struct BinNode *  LeftChild;
    struct BinNode *  NextSibling;
};
typedef struct BinNode *BinTree;

struct Collection
{
    int CurrentSize;
    BinTree TheTrees[ MaxTrees ];
};
typedef struct Collection *BinQueue;

BinQueue
Initialize( void )
{
    BinQueue H;
    int i;

    H = malloc( sizeof( struct Collection ) );
    if( H == NULL )
        printf( "Out of space!!!" );
    H->CurrentSize = 0;
    for( i = 0; i < MaxTrees; i++ )
        H->TheTrees[ i ] = NULL;
    return H;
}

/* Return the result of merging equal-sized T1 and T2 */
BinTree
CombineTrees( BinTree T1, BinTree T2 )
{
    if( T1->Element > T2->Element )
        return CombineTrees( T2, T1 );
    T2->NextSibling = T1->LeftChild;
    T1->LeftChild = T2;
    return T1;
}

/* Merge two binomial queues */
/* Not optimized for early termination */
/* H1 contains merged result, H2 would be cleared */
BinQueue
Merge( BinQueue H1, BinQueue H2 )
{
    BinTree T1, T2, Carry = NULL;
    int i, j;

    if( H1->CurrentSize + H2->CurrentSize > Capacity )
        printf( "Merge would exceed capacity" );

    H1->CurrentSize += H2->CurrentSize;
    for( 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: /* No trees */
        case 1: /* Only H1 */
            break;
        case 2: /* Only H2 */
            H1->TheTrees[ i ] = T2;
            H2->TheTrees[ i ] = NULL;
            break;
        case 4: /* Only Carry */
            H1->TheTrees[ i ] = Carry;
            Carry = NULL;
            break;
        case 3: /* H1 and H2 */
            Carry = CombineTrees( T1, T2 );
            H1->TheTrees[ i ] = H2->TheTrees[ i ] = NULL;
            break;
        case 5: /* H1 and Carry */
            Carry = CombineTrees( T1, Carry );
            H1->TheTrees[ i ] = NULL;
            break;
        case 6: /* H2 and Carry */
            Carry = CombineTrees( T2, Carry );
            H2->TheTrees[ i ] = NULL;
            break;
        case 7: /* All three */
            H1->TheTrees[ i ] = Carry;
            Carry = CombineTrees( T1, T2 );
            H2->TheTrees[ i ] = NULL;
            break;
        }
    }
    return H1;
}

/* Not optimized for O(1) amortized performance */
BinQueue
Insert( ElementType Item, BinQueue H )
{
    BinTree NewNode;
    BinQueue OneItem;

    NewNode = malloc( sizeof( struct BinNode ) );
    if( NewNode == NULL )
        printf( "Out of space!!!" );
    NewNode->LeftChild = NewNode->NextSibling = NULL;
    NewNode->Element = Item;

    OneItem = Initialize( );
    OneItem->CurrentSize = 1;
    OneItem->TheTrees[ 0 ] = NewNode;

    return Merge( H, OneItem );
}

ElementType
DeleteMin( BinQueue H )
{
    int i, j;
    int MinTree;   /* The tree with the minimum item */
    BinQueue DeletedQueue;
    BinTree  DeletedTree, OldRoot;
    ElementType MinItem;

    if( H->CurrentSize == 0 ) {
        printf( "Empty binomial queue" );
        return -Infinity;
    }

    MinItem = Infinity;
    for( i = 0; i < MaxTrees; i++ ) {
        if( H->TheTrees[ i ] &&
            H->TheTrees[ i ]->Element < MinItem ) {
            /* Update minimum */
            MinItem = H->TheTrees[ i ]->Element;
            MinTree = i;
        }
    }

    DeletedTree = H->TheTrees[ MinTree ];
    OldRoot = DeletedTree;
    DeletedTree = DeletedTree->LeftChild;
    free( OldRoot );

    DeletedQueue = Initialize( );
    DeletedQueue->CurrentSize = ( 1 << MinTree ) - 1;
    for( j = MinTree - 1; j >= 0; j-- ) {
        DeletedQueue->TheTrees[ j ] = DeletedTree;
        DeletedTree = DeletedTree->NextSibling;
        DeletedQueue->TheTrees[ j ]->NextSibling = NULL;
    }

    H->TheTrees[ MinTree ] = NULL;
    H->CurrentSize -= DeletedQueue->CurrentSize + 1;

    Merge( H, DeletedQueue );
    return MinItem;
}

#define MaxSize (12000)
int main( )
{
    BinQueue H;
    int i, j;
    ElementType AnItem;

    H = Initialize( );
    for( i=0, j=MaxSize/2; i<MaxSize; i++, j=( j+71)%MaxSize ) {
        printf( "Inserting %d\n", j );
        H = Insert( j, H );
    }
    j = 0;
    while( H->CurrentSize != 0 ) {
        printf( "DeleteMin\n" );
        if( DeleteMin( H ) != j++ )
            printf( "Error in DeleteMin, %d\n", j );
    }
    if( j != MaxSize )
        printf( "Error in counting\n" );
    printf( "Done...\n" );
    return 0;
}