<aside> 💡 What is heap? Heap is a region of memory used for dynamic memory allocation. In computer science, the heap is a portion of memory where programs can allocate memory dynamically at runtime.

</aside>

Advantages of heap-allocated memory

• Dynamic → The allocation size can be determined at run time
• Resizable → A heap allocation can be “resized”
• Duration → Heap allocations persist until they are freed
• Safety → If memory runs out, it can be detected and handled properly

malloc (memory allocation) obtains memory from the heap.

// malloc(s) requests s bytes of contiguous memory from the heap
// and returns a pointer to a block of s bytes, or
// NULL if not enough contiguous memory is available
// time: O(1) [close enough for this course]

free removes the memory allocated through malloc

// free(p) returns memory at p back to the heap
// requires: p must be from a previous malloc
// effects: the memory at p is invalid
// time: O(1)

Memory leaks occurs when allocated memory is not eventually freed

Garbage collector detects when memory is no longer in use and automatically frees memory and returns it to the heap. (C does not have a garbage collector!)

Dynamic Memory Side Effects & String I/O

Allocating and deallocating memory has a side effect: it modifies the “state” of the heap

// process_and_destroy_array(a, len) ...
// requires: a is a heap-allocated array
// effects: frees a (a is now invalid)

realloc resizes an array:

// realloc(p, newsize) resizes the memory block at p
//  to be newsize and returns a pointer to the
//   new location, or NULL if unsuccessful
// requires: p must be from a previous malloc/realloc
//   or NULL (then realloc behaves like malloc)
// effects: the memory at p is invalid (freed)
// time: O(n), where n is min(newsize, oldsize)

ADTs in C & Amortized Analysis

(More notes later!! Amortized analysis is pretty interesting…)