Program to implement a Fibonacci heap.

#include <stdlib.h> #include <stdio.h> typedef int key_t; typedef int object_t; typedef struct hp_n_t { key_t key; object_t *object; struct hp_n_t *left; struct hp_n_t *right; struct hp_n_t *up; struct hp_n_t *r_up; int rank; enum {complete, deficient} state; } heap_node_t; typedef heap_node_t node_t; #define BLOCKSIZE 256 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t […]

Continue reading

Program to implement binomial heap.

#include <stdlib.h> #include <stdio.h> typedef int key_t; typedef int object_t; typedef struct hp_n_t { int height; key_t key; object_t *object; struct hp_n_t *left; struct hp_n_t *right; } heap_node_t; typedef heap_node_t node_t; #define BLOCKSIZE 256 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL ) { […]

Continue reading

Program to implement a skew heap.

#include <stdlib.h> #include <stdio.h> typedef int key_t; typedef int object_t; typedef struct hp_n_t { key_t key; object_t *object; struct hp_n_t *left; struct hp_n_t *right; } heap_node_t; typedef heap_node_t node_t; #define BLOCKSIZE 256 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL ) { tmp = […]

Continue reading

Program to implement an leftist heap.

#include <stdlib.h> #include <stdio.h> typedef int key_t; typedef int object_t; typedef struct hp_n_t { int rank; key_t key; object_t *object; struct hp_n_t *left; struct hp_n_t *right; } heap_node_t; typedef heap_node_t node_t; #define BLOCKSIZE 256 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL ) { […]

Continue reading

Program to implement a search tree used as heap.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; typedef struct {key_t key; object_t *object; } heap_el_t; typedef struct {heap_el_t current_min; tree_node_t *tree; } heap_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; […]

Continue reading

Program to implement an orthogonal range tree.

#include <stdio.h> #include <stdlib.h> #define NEGINFTY -1000 #define BLOCKSIZE 256 typedef int object_t; typedef int number_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; number_t summand; number_t partial_sum; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( […]

Continue reading

Program to implement a weighted sum of intervals tree that supports interval-maximum queries.

#include <stdio.h> #include <stdlib.h> #define NEGINFTY -1000 #define BLOCKSIZE 256 typedef int object_t; typedef int number_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; number_t summand; number_t partial_sum; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( […]

Continue reading

Program to implement a weighted sum of intervals tree.

#include <stdio.h> #include <stdlib.h> #define NEGINFTY -1000 #define BLOCKSIZE 256 typedef int object_t; typedef int number_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; number_t summand; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; tree_node_t *get_node() { tree_node_t *tmp; if( free_list != […]

Continue reading

Program to implement an interval tree.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 struct intv {int low; int up; }; typedef struct intv object_t; typedef int key_t; typedef struct ls_n_t { key_t key; struct ls_n_t *next; object_t *object; } list_node_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; list_node_t *left_list; list_node_t *right_list; /* balancing information */ } […]

Continue reading

Program to implement a skip list.

#include <stdlib.h> #include <stdio.h> typedef int object_t; typedef int key_t; typedef struct tr_n_t { key_t key; struct tr_n_t *next; struct tr_n_t *down; } tree_node_t; typedef tree_node_t node_t; #define BLOCKSIZE 256 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list […]

Continue reading