1. 内容##

堆的实现

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 15/12/04.
//  Copyright © 2015年 YangKi. All rights reserved.

#include <iostream>
#include <set>
using namespace std;

class priqueue { // 维护的是最小堆
    int maxsize, size;
    int *arr;
    
    void swap(int a, int b)
    {
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    
    void up(int i)
    {
        while (i>1 && arr[i/2]>arr[i])
        {
            swap(i/2, i);
            i=i/2;
        }
    }
    
    void sink(int i)
    {
        while (2*i <= size)// have left son
        {
            int son=2*i;
            if(son+1<=size && arr[son]>arr[son+1]) son++;
            if(arr[i] <= arr[son]){ break;}
            swap(i, son);
            i=son;
        }
    }
    
public:
    priqueue(int m)
    {
        maxsize=m;
        arr=new int[maxsize+1];
        size=0;
    }
    
    void insert(int num)
    {
        if(size==maxsize)
        {
            cout<<"full!"<<endl;
            return;
        }
        
        arr[++size]=num;
        up(size);
    }
    
    void pop()
    {
        if(size==0)
        {
            cout<<"empty!"<<endl;
            return;
        }
        
        cout<<"min: "<<arr[1]<<endl;
        swap(1, size--);
        sink(1);
    }
};

int main()
{
    priqueue *p=new priqueue(10);
    p->insert(3);
    p->insert(7);
    p->insert(1);
    p->insert(4);
    p->insert(9);
    p->insert(4);
    
    p->pop();
    p->pop();
    p->pop();
    p->pop();
    p->pop();
    p->pop();
    return 0;
}

2. 习题##

extra###

O(log(n))时间计算出x^n的值？

int exp(int x, int n)
{
    if(n==0) return 1;
    else if( even(n))
        return square(exp(x, n/2));
    else
        return x*exp(x, n-1);
}