If (full & appendElement) => ✅ double the size. It takes O(n) .
✅ Amortized insertion time is still O(1)
to insert N elements to array with size N you need:
final capacity increase: n/2 elements to copy
previous capacity increase: n/4 elements to copy
previous capacity increase: n/8 elements to copy
...
second capacity increase: 2 elements to copy
first capacity increase: 1 elements to copy
in total you have total number of copies n/2+n/4+n/8+..+2+1<N
=> inserting N elements takes O(N) => O(1) on average
even though some insertions take O(N) in worst case
push - add the element ( O(1))
pop - take an element from the stack ( O(1))
peek - returns the item from the top of the stack without removing it
peek - returns the item from the top of the stack without removing it
LIFO (Last in, first out)
Stack
Implement Stack using LinkedList
Time: O(1)
Space: O(n)
Dynamic memory allocation: The size of the stack can be increased or decreased dynamically by adding or removing nodes from the linked list, without the need to allocate a fixed amount of memory for the stack upfront (which will be the case when we implement Stack using Array).
public class StackByLinkedList {
private static class Node {
int data;
public Node next;
}
Node top;
/**
* Initially: 1 <- 2 <- 3 (top pointer)
* After push: 1 <- 2 <- 3 <- new_value (top pointer)
*/
public Node push(int value) {
Node temp = new Node();
if (temp == null) {
System.out.println("Heap is full. Inserting an element would lead to stack overflow");
}
temp.data = value;
temp.next = top;
top = temp;
return temp;
}
public boolean isEmpty() {
return top == null;
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
} else {
return top.data;
}
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack is empty");
return -1;
} else {
int temp = top.data;
top = top.next;
return temp;
}
}
public void display() {
if (isEmpty()) {
System.out.println("Stack is empty");
return;
}
Node current = top;
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
}
public static void main(String[] args)
{
StackByLinkedList theStack = new StackByLinkedList();
theStack.push(11);
theStack.push(22);
theStack.push(33);
theStack.push(44);
theStack.display();
System.out.printf("\nTop element is %d\n", theStack.peek());
theStack.pop();
theStack.pop();
theStack.display();
System.out.printf("\nTop element is %d\n", theStack.peek());
}
}
Queue
FIFO (first in first out)
Dequeue - taking an element from the head
Enqueue - adding element to the tail
Peek - looking at head element, but not touching it
This is a complete (each level is filled up before another level is added and the levels are filled from left to right) binary tree based data structure.
Heaps are not sorted. There is no particular relationship between nodes at any level
Height of a tree with N nodes is O(logN)
When heap is useful
Heaps are used when the highest or lowest order/priority element needs to be removed. They allow quick access to this item in O(1) time. One use of a heap is to implement a priority queue.
Binary heaps are usually implemented using arrays, which save overhead cost of storing pointers to child nodes.
Cons of Using Heaps
Heaps only provide easy access to the smallest/greatest item. Finding other items in the heap takes O(n) time because the heap is not ordered. We must iterate through all the nodes.
Indexes computation
It’s parent is at the floor (i-1)/2 index.
floor - округление до целого в меньшую сторону (2.7 -> 2, -2.7 -> -3)
It’s left child is at 2 * i + 1 index.
It’s right child is at 2 * i + 2 index.
Insertion
until it finds a parent node that is smaller than it (Worst case is O(logN))
Deletion
The worst case scenario is that we have to traverse the entire tree. The cost of this is O(logN).
From array to Min Heap
The worst case time complexity will be O(n).
Building Max neap from arrays using Williams method LINK
Java Min Heap implementation
public class MinHeap {
private int capacity = 10;
private int size = 0;
int[] items = new int[capacity];
private int getLeftChildIndex(int parentIndex) {return 2 * parentIndex + 1;}
private int getRightChildIndex(int parentIndex) {return 2 * parentIndex + 2;}
private int getParentIndex(int childIndex) {return (childIndex-1) / 2;}
private boolean hasLeftChild(int index) {return getLeftChildIndex(index) < size;}
private boolean hasRightChild(int index) {return getRightChildIndex(index) < size;}
private boolean hasParent(int index) {return getParentIndex(index) >= 0;}
private int leftChild(int index) { return items[getLeftChildIndex(index)];}
private int rightChild(int index) { return items[getRightChildIndex(index)];}
private int parent(int index) { return items[getParentIndex(index)];}
private void swap(int indexOne, int indexTwo) {
int temp = items[indexOne];
items[indexOne] = items[indexTwo];
items[indexTwo] = temp;
}
private void ensureExtraCapacity() {
if (size == capacity) {
items = Arrays.copyOf(items, capacity * 2);
capacity *= 2;
}
}
public int peek() {
if (size == 0) throw new IllegalStateException();
return items[0];
}
//extract min element
public int poll() {
if (size == 0) throw new IllegalStateException();
int item = items[0];
items[0] = items[size-1];
size--;
heapifyDown();
return item;
}
public void add(int item) {
ensureExtraCapacity();
items[size] = item;
size++;
heapifyUp();
}
private void heapifyUp() {
int index = size - 1;
while (hasParent(index) && parent(index) > items[index]) {
swap(getParentIndex(index), index);
index = getParentIndex(index);
}
}
private void heapifyDown() {
int index = 0;
while (hasLeftChild(index)) { // if no left child => definitely no right child
int smallerChildIndex = getLeftChildIndex(index); // assume left is smaller
if (hasRightChild(index) && rightChild(index) < leftChild(index)) { // if right is smaller
smallerChildIndex = getRightChildIndex(index);
}
if (items[index] < items[smallerChildIndex]) {
break;
} else {
swap(index, smallerChildIndex);
}
index = smallerChildIndex;
}
}
}
class HashTable {
LinkedList[] data;
boolean put(String key, Person value) {
int hashCode = getHashCode(key);
int index = convertToIndex(hashCode); // e.g. hashCode % data.size()
// find proper linkedList for insertion
LinkedList list = data[index];
list.insert(key, value);
}
}
key => hashCode => index
Runtime
Worst case for look up is O(N), when there are a lot of collisions and you have just on LinkedList of all elements. For good implementations without collisions look up is O(1) .
HashTable vs HashMap
Resolve collisions
Collision when two keys after defining of index (hashCode () % mod) point to the same index.
Linear probing
Quadratic probing
Double hashing
Chaining
TreeMap
Key-Value data structure, where keys are stored in ascending order.
Internal implementation of TreeMap has nothing to do with HashMap. TreeMap is built on red-black tree.
