1 / \ 2 3 / \ / 5 6 7 Fig 1It's clear that it supports O(log N) operations.
1 / \ 3 2 / / 5 7 / 6 Fig 2It's neither complete nor balanced. Yet, it supports O(log N) operations too!
vector<int> stree(4*N + 1,0); vector<int> arr(N + 1,0); int build(int i, int j, int k) { if(i == j) { stree[k] = i; return stree[k]; } int mid = (i+j)/2; int left=-1,right=-1; left = build(i,mid,2*k); right = build(mid+1,j,2*k+1); if(arr[left] > arr[right]) stree[k] = right; else stree[k] = left; return stree[k]; } int rmq(int p, int i, int j, int L, int R) { //invalid query if(i > R || j < L) return -1; if(i <= L && R <= j) return stree[p]; int mid = (L+R)/2; int left = rmq(2*p, i, j, L, mid); int right = rmq(2*p + 1, i, j, mid+1, R); if (left == -1) return right; if (right == -1) return left; return (arr[left] < arr[right]) ? left : right; }
//Implementation of Min-Binary Heap //Support: Insert, Pop, Top #include <iostream> #include <cstdio> #include <string> using namespace std; class MinHeap { private: typedef int pos; static const pos NIL = 0; int max_size; //max size of array pos last; //position of last element int *minheap; //pointer to an array //MinHeap Construction Algorithm void upheap(pos x); void downheap(pos x); pos left_child(pos x); pos right_child(pos x); pos parent(pos x); void heapswap(pos x, pos y); public: MinHeap(int sz): max_size(sz), minheap(new int[sz+1]), last(NIL){} ~MinHeap() { delete[] minheap; } void push(int m); void pop(); int top(); bool empty(); void to_string(); }; MinHeap::pos MinHeap::left_child(pos x) { if(2*x > last) return NIL; return 2*x; } MinHeap::pos MinHeap::right_child(pos x) { if(2*x + 1 > last) return NIL; return 2*x + 1; } MinHeap::pos MinHeap::parent(pos x) { if(x == 1) return NIL; return x/2; } void MinHeap::heapswap(pos x, pos y) { int temp = minheap[x]; minheap[x] = minheap[y]; minheap[y] = temp; } void MinHeap::upheap(pos x) { pos par = parent(x); while (par != NIL && minheap[par] > minheap[x]) { heapswap(x,par); x = parent(x); } } void MinHeap::downheap(pos x) { pos next = x; pos left = left_child(x); pos right = right_child(x); if(left != NIL && minheap[left] < minheap[next]) next = left; if(right != NIL && minheap[right] < minheap[next]) next = right; if(next == x) return; heapswap(x, next); downheap(next); } //Function definitions void MinHeap::push(int m) { if(last+1 > max_size) { printf("MinHeap is already full, insertion is aborted\n"); return; } ++last; minheap[last] = m; upheap(last); } int MinHeap::top() { if(last < 1) { printf("MinHeap is empty\n"); return NIL; } return minheap[1]; } void MinHeap::pop() { if(empty()) return; minheap[1] = minheap[last]; --last; downheap(1); } void MinHeap::to_string() { for(pos it = 1; it <= last; ++it) { printf("%d ", minheap[it]); } printf("\n"); } bool MinHeap::empty() { if(last == NIL) return true; return false; } int main() { /** * TEST BODY * 3 Commands: Push, Pop, and Top */ printf(":::::::::::MinHeap:::::::::::\n 2014 - Prajogo Tio \n Simple Implementation of MinHeap\n\n"); printf("Enter the intended size of the MinHeap: "); int max_sz; cin >> max_sz; MinHeap myHeap(max_sz); printf("Command:\n"); printf("1. push <number>\n2. top\n3. pop\n4. quit\n\n"); string cmd; int num; while(printf("Key in your command: \n"), cin >> cmd) { if( cmd == "quit") { printf("Program is terminating. See you again.\n\n"); break; } if( cmd == "push") { cin >> num; myHeap.push(num); cout << num << " has been pushed to the heap\n\n"; } else if( cmd == "pop") { myHeap.pop(); cout << "Top element has been removed\n\n"; } else if( cmd == "top") { if(myHeap.empty()) { cout << "MinHeap is empty\n\n"; } else { cout << "Top element: " << myHeap.top() << endl << endl; } } } return 0; }
vector<int> ftree(11,0); int maxval; int lsb(int i) { return i & (-i); } void update(int i, int val) { while(i <= maxval) { ftree[i] += val; i = i + lsb(i); } } int cumfreq(int i) { int tot = 0; while( i > 0) { tot += ftree[i]; i = i - lsb(i); } return tot; }
#include <cstdio> #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; //Implementation of Suffix Automaton //First Try, Must be very INEFFICIENT //Using pointers maybe struct state; struct edge; state* split(state* parent, state* child, vector<edge*>::iterator it); struct edge { state* child; char label; }; struct state { //information regarding the state int index; int pos; //suffix link state* suff; //prim edge vector<edge*> prim_edge; //sec edge vector<edge*> sec_edge; }; state *root, *sink; int idx = 1; void init(string str) { //create the root state root = new state; root->suff = NULL; root->prim_edge.clear(); root->sec_edge.clear(); root->index = 0; root->pos = -1; //initialize sink sink = root; int len = str.size(); for(int i=0;i<len;++i) { //edge label char a = str[i]; state* newsink = new state; newsink->index = idx++; newsink->pos = i; newsink->suff = NULL; //initialize new edge to the new sink edge* to_newsink = new edge; to_newsink->child = newsink; to_newsink->label = a; sink->prim_edge.push_back(to_newsink); state* currstate = sink; while( currstate->suff != NULL && newsink->suff == NULL) { currstate = currstate->suff; bool finished = false; //if exist prim_edge of currstate with label == a for(vector<edge*>::iterator it = currstate->prim_edge.begin(); it != currstate->prim_edge.end(); ++it) { if( (*it)->label == a ) { //update suff link of newsink to currstate newsink->suff = (*it)->child; finished = true; break; } } if( finished ) break; //if exist secondary edge for(vector<edge*>::iterator it = currstate->sec_edge.begin(); it != currstate->sec_edge.end(); ++it ) { if( (*it)->label == a ) { //split the state state* child = (*it)->child; state* clone = split(currstate, child, it); //update suffix link of newsink to clone newsink->suff = clone; finished = true; break; } } if( finished ) break; //Else, add secondary edge to newsink and continue currstate->sec_edge.push_back(to_newsink); } //if newsink still does not have suffix link if (newsink->suff == NULL) { //point to source newsink->suff = root; } //update sink sink = newsink; } } state* split(state* parent, state* child, vector<edge*>::iterator iter) { state* clone = new state; clone->index = idx++; clone->pos = child->pos; char label = (*iter)->label; //copy all outgoing edge for(vector<edge*>::iterator it = child->prim_edge.begin(); it != child->prim_edge.end();++it) { edge* e = new edge; e->label = (*it)->label; e->child = (*it)->child; clone->sec_edge.push_back(e); } for(vector<edge*>::iterator it = child->sec_edge.begin(); it != child->sec_edge.end();++it) { edge* e = new edge; e->label = (*it)->label; e->child = (*it)->child; clone->sec_edge.push_back(e); } //update suffix link of clone clone->suff = child->suff; //update suffix link of child child->suff = clone; //update parent's sec edge to child to prim edge to clone parent->sec_edge.erase(iter); edge* to_clone = new edge; to_clone->label = label; to_clone->child = clone; parent->prim_edge.push_back(to_clone); //update all edge to child to point to clone state* currstate = parent; while( currstate->suff != NULL ) { currstate = currstate->suff; bool update = false; for(vector<edge*>::iterator it = currstate->sec_edge.begin(); it != currstate->sec_edge.end(); ++it) { if( (*it)->child == child ) { (*it)->child = clone; update = true; break; } } if( !update ) break; } return clone; } void print(state* s) { printf("state with index: %d\n", s->index); vector<edge*>::iterator it; for(it = s->prim_edge.begin(); it != s->prim_edge.end(); ++it) { printf( "==%c (%d)" , (*it)->label, (*it)->child->index); printf("\n"); } for(it = s->sec_edge.begin(); it != s->sec_edge.end(); ++it) { printf( "--%c (%d)" , (*it)->label, (*it)->child->index); printf("\n"); } for(it = s->prim_edge.begin(); it != s->prim_edge.end(); ++it) { print((*it)->child); } for(it = s->sec_edge.begin(); it != s->sec_edge.end(); ++it) { print((*it)->child); } } int search(string str) { int len = str.size(); state* currstate = root; for(int i=0;i<len;++i) { vector<edge*>::iterator it; bool found = false; for(it = currstate->prim_edge.begin(); it!= currstate->prim_edge.end(); ++it) { if( (*it)->label == str[i] ) { currstate = (*it)->child; found = true; break; } } if( found ) continue; for(it = currstate->sec_edge.begin(); it!= currstate->sec_edge.end(); ++it) { if( (*it)->label == str[i] ) { currstate = (*it)->child; found = true; break; } } if (!found) return -1; } return currstate->pos; } int main() { printf("Welcome to SUFFIX AUTOMATON SEARCH\n"); printf("Enter your string/dictionary\n"); string str; getline(cin,str); init(str); string src; while (1) { printf("Enter your search term:\n"); getline(cin,src); int pos = search(src); if(pos < 0) { printf("The term is not found\n"); } else { printf("The term is found at end-pos: %d\n", pos); } } return 0; }
init(): input: none output: initialize the disjoint set data structure for i in 1 to N: parent[i] = iThe union of 2 elements will result in parent of the first element pointing to the second element. As this procedure proceeds, a forest of trees will result, where each tree is a representation of a set. Now imagine if we want to check if 2 element is indeed inside the same tree, that means we need to traverse up the parent chain of each element until we find an element which parent points to itself (hence the root of the tree) and finally compare whether the two roots are the same. This traversal may take \(O(\log{N})\) each time (the height of the tree). Hence we need to compress this tree such that subsequent check of the root of a tree will result in \(O(1)\) average. Call this procedure find(u) as described below:
find(u): input: an element output: the root of the disjoint set it is in if u != parent[u]: parent[u] = find(parent[u]) return parent[u]Here we check whether \(u\) is root, if so then we return \(u\). Otherwise, we need to update the parent of u to point to the root of the tree, and return it. Hence it updates the parent-child relationship in the tree such that the tree is compressed to a flatter tree.
union(u,v): input: 2 elements u,v output: union of the set containing u and the set containing v parent[find(u)] = find(v) same(u,v): input: 2 elements u,v output: is u and v in the same set? return find(u) == find(v)Here is a minimalist implementation of the data structure:
vector<int> p(100); vector<int> r(100); int init() { for (int i=0;i<100;++i) p[i]=i, r[i] = 0; } int find_set(int i) { return (p[i] == i) ? i : (p[i] = find_set(p[i])); } bool same_set(int i, int j) { return find_set(i) == find_set(j); } void union_set(int i, int j) { if ( same_set(i,j) ) return; int x = find_set(i); int y = find_set(j); if(r[x] > r[y]) { p[y] = x; } else { p[x] = y; if (r[x] == r[y]) ++r[y]; } }
/* Linked List Simple Implementation */
struct node{
int key;
node* next;
};
class llist{
public:
node* head; //starting point
node* tail; //ending signal
llist(){
head=new node();tail=new node();
head->next=tail; //initially, head points to tail(empty linked list)
tail->next=tail; //tail points to itself
}
void del_next(node* n){
node* t=n->next;
n->next=t->next;
delete t; //freeing up memory
}
node* ins_next(node* n,int value){
node* t=new node();
t->key=value;
t->next=n->next;
return n->next=t; // returning "iterator" to last entry
}
};
#define MS 1000
int key[MS];
int next[MS];
int size,head,tail;
void link_init(){
head=0;tail=1;size=2;
next[head]=tail;
next[tail]=tail;
}
void del_next(int node){
next[node]=next[next[node]];
}
int ins_next(int node, int value){
key[size]=value;
next[size]=next[node];
next[node]=size;
return size++;
}