objectdisorientedprogrammer / c-data-structures Goto Github PK

Create a binary tree data structure.

Add license header to all source files.

Make it easy to build and test the code.

Add dependencies and build instructions to the readme along with better documentation or each data structure,

Make some unit tests for the binary tree implementation. Relates to #12.

Basic

• find-max or find-min: find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
• insert: adding a new key to the heap (a.k.a., push[3])
• extract-max [or extract-min]: returns the node of maximum value from a max heap [or minimum value from a min heap] after removing it from the heap (a.k.a., pop[4])
• delete-max [or delete-min]: removing the root node of a max heap [or min heap], respectively
• replace: pop root and push a new key. More efficient than pop followed by push, since only need to balance once, not twice, and appropriate for fixed-size heaps.[5]

Creation

• create-heap: create an empty heap
• heapify: create a heap out of given array of elements
• merge (union): joining two heaps to form a valid new heap containing all the elements of both, preserving the original heaps.
• meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.

Inspection

• size: return the number of items in the heap.
• is-empty: return true if the heap is empty, false otherwise.

Internal

• increase-key or decrease-key: updating a key within a max- or min-heap, respectively
• delete: delete an arbitrary node (followed by moving last node and sifting to maintain heap)
• sift-up: move a node up in the tree, as long as needed; used to restore heap condition after insertion. Called "sift" because node moves up the tree until it reaches the correct level, as in a sieve.
• sift-down: move a node down in the tree, similar to sift-up; used to restore heap condition after deletion or replacement.

(from https://en.wikipedia.org/wiki/Heap_(data_structure))

Write tests for basic functionally of all data structures. Use assert.h or similar.

Organized the code better so that each data structure is in its own folder with all dependencies.

Use the inputs from program.txt to create unit tests verifying that the strings are valid.

Split the c file into c and h.

The max heap has no function to remove the max value and return the max value at the same time.
Implement a new function that does this:

int extractMax(); // similar to pop()

Split the c file into c and h.