Posts

Showing posts with the label Data Structures

Tree

Image
  A  Tree  is a non-linear, hierarchical data structure that consists of a collection of  nodes  connected by  edges .   Unlike linear structures (like arrays or linked lists), which store data in a sequential line, trees organize data in a "branching" way that resembles an actual tree - though in computer science, we usually draw them "upside down" with the root at the top.

Heap

Image
 A heap is a  special tree-based data structure  that satisfies two rules: 1.  Heap Property Depending on the type of heap: Min-Heap Every parent node is less than ( ≤)  it's children. The smallest element is always at the  root . Max-Heap Every parent node is  ≥  its children. The largest element is always at the  root . It does  not  require a fully sorted structure, only the parent/child relationship must follow the rule. 2.  Complete Binary Tree Property A heap is always a  complete binary tree , meaning: It is filled  level by level , from left to right. No gaps are allowed except possibly at the last level. This makes it easy to store a heap inside an  array  without needing pointers. How a Heap Is Stored in an Array For a node at index  i : Left child = index  2i Right child = index  2i + 1 Parent = index  i // 2 This mapping is why heaps work efficiently inside arrays.