A binary heap implementation written in C with simple interface. Cranberry Heap can be used as a min or max heap. A binary heap is a binary tree like data structure that stores elements in specific order and useful for quickly answering queries about the maximum or the minimum elements. Visit Wikipedia to know more.
- n: the number of elements in the heap
- Creation: creates a new heap data structure, Min or Max as specified by the user. Performance: O(1)
- Insertion: inserts a new element in the heap. Performance: O(log(n))
- Deletion: deletes an existing element in the heap. Performance: O(n)
- Extraction: removes the min/max element in the heap. Performance: O(log(n))
- peek: returns the min/max element without removing it. Performance: O(1)
- clear: removes all the elements from the heap. Performance: O(n)
- contains: checks if an element is present in the heap. Performance: O(n)
| Return | Function and Description |
|---|---|
| struct cranbheap* |
cbh_create(int (* comparator)(void*, void*)) Creates a new cranberry heap structure |
| void |
cbh_insert(struct cranbheap* cbh, void* obj) Inserts a new element in the heap |
| void* |
cbh_delete((struct cranbheap* cbh, void* obj) deletes an element from the heap |
| void* |
cbh_extractmw(struct cranbheap* cbh) removes the root element from the heap (i.e maximum/minimum element) |
| void* |
cbh_peek(struct cranbheap* cbh) removes the root element from the heap (i.e maximum/minimum element) |
| void |
cbh_clear(struct cranbheap* cbh) removes all the elements from the heap |
| bool |
cbh_contains(struct cranbheap* cbh, void* obj) returns true if obj is store in the heap |
| unsigned int |
cbh_length(struct cranbheap* cbh) returns the number of elements store in the heap |
cranbheap cbh_create(int ( comparator)(void*, void*))** Creates a new cranberry heap structure
Pointer to the created heap
int (* comparator)(void*, void*): a pointer to a function that takes as an argument two void* pointers (the objects stored in the tree will be passed to this function) and returns an int according to the following rules:
- if the first argument should come before the second argument return -1
- if the first argument should come after the second argument return 1
- if both have the same weight return 0
This function will be used to order the objects in the heap
void cbh_insert(struct cranbheap cbh, void obj)** Inserts a new object in the tree
- struct cranbheap* cbh: pointer to the heap
- void* obj: object to be inserted in the heap
void cbh_delete((struct cranbheap cbh, void* obj)** Deletes a specific object from the heap
the deleted object if it exits, or NULL if the object was not found
- struct cranbheap* cbh: pointer to the heap
- void* obj: the object to be removed from the heap
void cbh_extractmw(struct cranbheap cbh)** Extracts the the maximum/minimum element (specified by the comparator) from the tree
returns a pointer to the maximum/minimum element
- struct cranbheap* cbh: pointer to the heap
void cbh_peek(struct cranbheap cbh)** Retrieves but does not remove the head of the heap
returns a pointer to the head of the heap
- struct cranbheap* cbh: pointer to the heap
void cbh_clear(struct cranbheap cbh)* Removes all the elements from the heap
- struct cranbheap* cbh: pointer to the heap
bool cbh_contains(struct cranbheap cbh, void obj)**
checks if the given element is present in the heap
returns true if the given object is present in the heap, false otherwise
- struct cranbheap* cbh: pointer to the heap
- void* obj: pointer to the object to be searched for
unsigned int cbh_length(struct cranbheap cbh)* gets the number of elements stored in the heap
the number of void* objects stored in the heap
- struct cranbheap* cbh: pointer to the heap
- Clone this repository or download it as zip and extract it.
- open up the terminal and
cdinto the project's directory. - run:
make - run:
sudo make install
compilation: clang your_program.c -lcranbheap -o your_program
where -lcranbheap tells the compiler where to find the code for the library
Uninstall
To uninstall the library run the following command in the terminal:
sudo make uninstall
if you are planning to contribute, it is highly recommended that you read through the docs and go through the CONTRIBUTING.md guidlines
For this project, there are three main types of issues that you can open:
Please follow the format proposed by these templates before opening a new issue.
Please follow that pull request guidelines specified in The pull Request template
- “uthash" by Troy D. Hanso is licensed under BCD
For any inquiries please send me at: abdullahem1997@hotmail.com