heap.h

模拟器提供了一个简单易用的平台

/*
 * File: heap.h
 * Author: Suman Banerjee <[e-mail]>
 * Date: July 31, 2001
 * Terms: GPL
 *
 * myns simulator
 */

#ifndef _HEAP_H_
#define HEAP_H_

enum TreeDirection {
    LEFT,
    RIGHT,
    INVALID
};

struct HeapElement {
  void *key;
  long int unique;
  void *value;

  HeapElement *left;
  HeapElement *right;
  HeapElement *parent;
};

struct Heap {
  HeapElement *root;
  int num_elements;
  int completed_levels;
};

Heap *init_heap (void);
void delete_heap (Heap *h);
void delete_tree (HeapElement *he);
bool is_empty (Heap *h);
TreeDirection locate_parent_for_next_insert (Heap *h, HeapElement*& p);
void exchange_node_with_parent (Heap *h, HeapElement *he);
void exchange_nodes (Heap *h, HeapElement *h1, HeapElement *h2);
void* heap_insert (Heap *h, void *key, void *value, int (*compare_fn)(void*,void*));
void heapify_upwards (Heap *h, HeapElement *he, int (*compare_fn)(void*,void*));
void heapify_downwards (Heap *h, HeapElement *he, int (*compare_fn)(void*,void*));
void output_heap (Heap *h, void (*output_fn)(void*));
void traverse_heap (HeapElement *he, int levels, void (*output_fn)(void*));

void heap_lookup_data (void *pos, void*& key, void* & value);
void heap_lookup_min (Heap *h, void*& key, void* & value);
int heap_extract_data (Heap *h, void* pos, void*& key, void*& value, int (*compare_fn)(void*,void*));
int heap_extract_min (Heap *h, void*& key, void*& value, int (*compare_fn)(void*,void*));
void* locate_data (Heap *h, void *value);
void* locate_data_in_subtree (Heap *h, HeapElement *he, void *value);

int compare_function_wrapper (long int u1, void * k1, long int u2, void * k2, int (*compare_fn)(void*,void*));

int heap_menu (void);
int cmp (int n1, int n2);

#endif