CPSC 259 FInal

please let me pass

Binary Heap

Binary Heap

Complete Binary Tree

Hashing Formula

Binary Heap: Min Heap

Value of a node is no greater than its childrens values

Binary Heap: Max Heap

Value of a node is at least as large as its childrens values

Perfect tree

full and complete

full tree

every node has 0 or 2 childrena binary tree where every node has either zero or two children

complete tree

all leaves are full except last level

max nodes in a tree

n = (k^h-1)/(k-1)
n = max nodes

k = #ary

h = height

min heap formulas

child >= parent

remove min/max for heap

1. replace root with last in array

2. bubble down

   1. for min heap swap with smaller child (child >= parent)

   2. max heap swap with bigger child (parent >= child)

insertion for heaps

• Add the new element to the end of the heap (next available position).

• Bubble up the new element to restore the heap property:

PreOrder Traversal

InOrder Traversal

PostOrder Traversal

max nodes in a tree

height of a tree

max size of a tree

setting up a dummy node with malloc

struct listNode* result = = (struct ListNode*)malloc(sizeof(struct ListNode));