Interfaces:

Deque:

Deque(): cria e devolve uma deque vazia
PushFront(d,x): insere x no extremo front de d
PushBack(d,x): insere x no extremo back de d
PopFront(d): remove o elemento no extremo front de d
PopBack(d): remove o elemento no extremo back de d
Front(d): devolve o elemento no extremo front de d
Back(d): devolve o elemento no extremo back de d
Kth(d,k): k-ésimo elemento de d, onde o front é o primeiro elemento de d
Print(d): imprime todos os elementos da deque d na mesma linha, separados por um branco
          (não precisa se preocupar com eventual espaço em branco no fim da linha)

Treap:

Treap(): cria e devolve uma treap vazia
Insert(r,x): insere x na treap com raiz r
Delete(r,x): remove x da treap com raiz r
Search(r,x): true se x está na treap com raiz r e false caso contrário
Min(r): menor chave presente na treap com raiz r
Print(r): imprime todos os elementos na treap com raiz r.
          para a impressão ser mais visual, acione uma rotina recursiva printRec(u, i)
          que aciona printRec(u.esq, i+3), imprime numa linha o valor (e a prio) da raiz
          depois de i espaços em branco, e depois aciona printRec(u.dir, i+3). 
          Se não entendeu a descrição e o objetivo, pergunte na aula ou no fórum.

Pilha:

Stack(): cria e devolve uma pilha vazia
Push(p,x): empilha x na pilha p
Pop(p): desempilha um elemento de p
Size(p): número de elemento em p
Top(p): elemento do topo de p
Kth(p,k): k-ésimo elemento de p, onde o topo é o primeiro elemento de p
Print(p): imprime todos os elementos da pilha p

Pilha retroativa:

retroStack(): cria e devolve uma pilha retroativa vazia
insert(t, "Push", x): insere um "empilha x" na sequência de modificações no instante t
insert(t, "Pop"): insere um "pop" na sequência de modificações no instante t
delete(t): remove da sequência de modificações a operação do instante t
size(t): número de elemento na pilha retroativa no instante t
top(t): elemento do topo da pilha retroativa no instante t
kth(t,k): k-ésimo elemento da pilha retroativa no instante t

Árvore de segmentos estática:

AS(S): cria uma árvore de segmentos para o conjunto S de intervalos
Segments(r,x): devolve uma lista com os segmentos na AS r que contém x
Print(r): imprime a AS r, com a lista de segmentos para cada nó

Árvore de segmentos dinâmica:

ASD(): cria e devolve uma AS dinâmica vazia
Segments(r,x): devolve uma lista com os segmentos na AS dinâmica r que contém x
Insert(r,s): insere na AS dinâmica r o intervalo s
PrintADS(r): aciona o Print para cada AS da ASD r

Árvore splay:

ST(): cria e devolve uma splay tree vazia
Insert(r,x): insere x na ST com raiz r
Delete(r,x): remove x da ST com raiz r
Search(r,x): true se x está na ST com raiz r e false caso contrário
Min(r): menor chave presente na ST com raiz r
Print(r): imprime todos os elementos na ST com raiz r
Split(r,x): divide a splay tree de raiz r em duas, uma com as chaves ≤ x e outra com as chaves > x; devolve as raízes das duas splay trees resultantes.
Join(r1,r2): junta as splay trees enraizadas em r1 e r2, assumindo que todas as chaves na árvore r1 são menores ou iguais às de r2.

Treap com split e join:

Treap(): cria e devolve uma treap vazia
Insert(r,x): insere x na treap com raiz r
Delete(r,x): remove x da treap com raiz r
Search(r,x): true se x está na treap com raiz r e false caso contrário
Min(r): menor chave presente na treap com raiz r
Print(r): imprime todos os elementos na treap com raiz r.
Split(r,x): divide a treap de raiz r em duas, uma com as chaves ≤ x e outra com as chaves > x; devolve as raízes das duas treaps resultantes.
Join(r1,r2): junta as treaps enraizadas em r1 e r2, assumindo que todas as chaves na árvore r1 são menores ou iguais às de r2.

As implementações das rotinas Insert e Delete devem usar as rotinas Split e Join.

Algoritmo Guloso:

GreedyASS(n,m,x): recebe inteiros n e m, e um vetor x[1..m] com inteiros entre 1 e n representando a sequência de pontos (1,x[1]),...,(m,x[m]), e imprime o conjunto arboreamente satisfeito contendo estes pontos, obtido do algoritmo guloso visto em aula. Os pontos devem ser impressos em ordem crescente de y-coordenada.

Certificação de conjunto arboreamente satisfeito:

CheckASS(t,x,y): que recebe um inteiro t, e dois vetores x[1..t] e y[1..t] com as coordenadas de t pontos, sendo que y[1..t] está em ordem crescente, e que imprime SIM se estes t pontos formam um conjunto arboreamente satisfeito e, caso contrário, imprime um par de pontos dados que descreve um retângulo arboreamente insatisfeito.

Adicionalmente, seu programa deve ter uma opção de compilação DEBUG que, se acionada, faz com que a rotina CheckASS imprima, antes de processar os pontos com cada x-coordenadas, o estado da treap interna que é mantida pelo algoritmo.

Heap cinético:

KinHeap(id, x0, speed, n): cria um maxheap cinético com n elementos,
  com identificador, valor inicial e velocidade nos vetores id, x0 e speed. 
Advance(t): avança o tempo para o instante t
Change(id, v): altera a velocidade do elemento id para v
Insert(id, xnow, v): insere o elemento id na posição xnow com velocidade v
Max(): identificador do elemento com o maior valor no instante atual
DeleteMax(): remove o elemento com o maior valor
Delete(id): remove o elemento id
Print(): imprime o heap no instante atual