computer-science

Computer science studies helpers.
Have fun :)

FIAR-Minimax

A C implementation of Four-In-a-Row (CLI), user versus computer, and the minimax algorithm. The computer steps are being calculated and chosen by the algorithm. The player may enter the level of difficulty, which implies the depth of the minimax tree.

Further Reading:

• The minimax algorithm

RBTree

A Java implementation of red-black tree with following operations: insertion, deletion, search , successor, predecessor, minimum and maximum. The tree nodes are instances of classes which extend RBTreeNode class.

This data structure is based on "Introduction to Algorithms" book, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Further Reading:

• Red-Black Tree

MaxDHeap

A simple, non-generic and minimalist implementation of the heap sort algorithm using d-ary maximum heap, to sort an array of integers.

"A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children." (problem 6.2, "Introduction to Algorithms", by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein)

Indexes Explained

Let A[0..n-1] be the heap array (the heap size is n).
In d-ary heap, the index of the k'th son of node A[i] is:

(skipping the children of the previous i-1 nodes)

---

The index of the parent of A[i] is:

Proof:
Let p be the index of the parent of A[i]. Then:

--- The **first leaf** of the heap is in index:

Proof:
The index of the first son of A[i] is:

Which means that it's out of the array bounds.
In addition, for:

The first son index is:

Which means it's within the array bounds.

Because heap is an almost-full binary tree, we derive that i is the index of the first leaf.