# (DD03) heaps — Class Detailed Design [245 LOC]

| Field | Value |
|-------|-------|
| Fully Qualified Name | `algo_Calc.heaps` |
| Layer | Utility |
| Module | `algo_Calc` |

## Class Overview

The `heaps` class provides the heap-sort implementation used by the sorting demo package. It contains a recursive `heapify` routine that enforces the max-heap property and a `heapSort` routine that first builds the heap and then extracts the maximum element until the array is sorted. The class is algorithmic and state-free: it works only on the provided integer array and size parameters, without persisting any object state.

---

## Method: heapify(int num[], int size, int i)

### 1. Role
This method restores the max-heap property for the subtree rooted at index `i`. It compares the current node with its left and right children, swaps the largest value into the root position when needed, and then recursively repairs the affected child subtree.

### 2. Processing Pattern
```mermaid
flowchart TD
A["heapify called with num, size, i"] --> B["Set largest to i"]
B --> C["Compute left child as 2 * i + 1"]
C --> D["Compute right child as 2 * i + 2"]
D --> E["Check left child is inside heap and greater than current largest"]
E --> F["Check right child is inside heap and greater than current largest"]
F --> G["largest changed"]
G --> H["Swap num[i] and num[largest]"]
H --> I["Recursively call heapify on the swapped child"]
F --> J["largest unchanged"]
J --> K["Return without further action"]
```

### 3. Parameter Analysis
| Parameter | Type | Direction | Meaning | Constraints |
|---|---|---|---|---|
| `num` | `int[]` | In/out | Array representing the heap data structure | Must not be `null`; indices referenced by the method must be valid |
| `size` | `int` | In | Effective heap size within `num` | Must be between `0` and `num.length` |
| `i` | `int` | In | Root index of the subtree to repair | Must identify a valid node inside the heap boundary |

### 4. CRUD Operations / Called Services
| Category | Details |
|---|---|
| Read | Reads `num[i]`, `num[left]`, and `num[right]` to compare heap values |
| Update | Swaps array elements when the subtree violates the heap property |
| Create | None |
| Delete | None |
| Called Services | None; the method only invokes itself recursively |

### 5. Dependency Trace
| Type | Member | Relation |
|---|---|---|
| Internal call | `heapify(int num[], int size, int i)` | Self-recursive repair after a swap |
| Internal caller | `heapSort(int num[], int size)` | Invokes `heapify` during heap construction and after extracting the maximum |
| External callers | Not identified from the provided source excerpt | The class is package-private, so call sites are likely within `algo_Calc` |

### 6. Per-Branch Detail Blocks
- **Initial state block**: `largest` starts as `i`, which means the method assumes the current node is the best candidate until comparisons prove otherwise.
- **Left-child comparison block**: If `left < size` and `num[left] > num[largest]`, the left child becomes the new best candidate. This prevents reading beyond the active heap boundary.
- **Right-child comparison block**: If `right < size` and `num[right] > num[largest]`, the right child can replace either the current node or the left child as the new largest value.
- **Swap-and-recurse block**: When `largest != i`, the node at `i` is swapped with the largest child, and the method recurses into that child index to continue pushing the displaced value downward.
- **No-op block**: If neither child is larger than the current node, the subtree already satisfies the max-heap property and the method exits immediately.

---

## Method: heapSort(int num[], int size)

### 1. Role
This method sorts an integer array in ascending order using the heap-sort algorithm. It first converts the array into a max heap, then repeatedly moves the largest element from the root to the end of the active region and restores the heap on the reduced prefix.

### 2. Processing Pattern
```mermaid
flowchart TD
A["heapSort called with num and size"] --> B["Set i to size / 2 - 1"]
B --> C["Call heapify for each internal node down to index 0"]
C --> D["Set i to size - 1"]
D --> E["Swap num[0] with num[i]"]
E --> F["Call heapify on the reduced heap with boundary i"]
F --> G["Decrement i"]
G --> H["More elements remain"]
H --> E
G --> I["All elements extracted"]
I --> J["Return sorted array in place"]
```

### 3. Parameter Analysis
| Parameter | Type | Direction | Meaning | Constraints |
|---|---|---|---|---|
| `num` | `int[]` | In/out | Array to be sorted in place | Must not be `null`; elements are reordered in the same buffer |
| `size` | `int` | In | Number of active elements to sort | Must match the portion of the array intended for sorting |

### 4. CRUD Operations / Called Services
| Category | Details |
|---|---|
| Read | Reads array values during heap construction and extraction |
| Update | Swaps root and tail elements, then re-heaps the remaining prefix |
| Create | None |
| Delete | None |
| Called Services | Calls `heapify(int num[], int size, int i)` repeatedly |

### 5. Dependency Trace
| Type | Member | Relation |
|---|---|---|
| Internal call | `heapify(int num[], int size, int i)` | Used to build the initial heap and to restore heap order after each extraction |
| External callers | Not identified from the provided source excerpt | The method is package-private and likely invoked from the GUI action logic in `Sortingss` |

### 6. Per-Branch Detail Blocks
- **Heap construction block**: The first loop starts at `size / 2 - 1`, which is the last internal node. This ensures all leaf-only subtrees are skipped because they already satisfy heap order.
- **Extraction block**: Each iteration swaps the current maximum at `num[0]` with `num[i]`, placing the largest unsorted element at the end of the array.
- **Repair block**: After the swap, `heapify(num, i, 0)` restores the heap property only within the shrinking prefix `[0, i)`. The sorted suffix remains untouched.
- **Termination block**: When `i` reaches `0`, the algorithm has fully placed every element, and the array is sorted in place.