Heap

07 Sep 2022 in Study / Computer science on Heap

Data Structure

• Complete Binary Tree : Almost symmetric tree (parent node has at most 2 child nodes)
• Loosely sort
• Max heap
  • Parent Node’s value >= Child Node’s value
    
    
• Min heap
  • Parent Node’s value <= Child Node’s value
    
    

Implementation Idea

• Using array (or list)
• Using index of array
  • Parent node’s index == left or right child node’s index / 2 (quotient)
  • Left child node’s index == 2 x parent node’s index (if start index == 0 » 2 x parent node’s index + 1)
  • Right child node’s index == 2 x parent node’s index + 1 (if start index == 0 » 2 x parent node’s index + 2)
    
    

Implementation With Java

• Max heap is similar to min heap in terms of implementation except for being max
• Min heap

class minHeap{
	private ArrayList<Integer> heap;

	public minHeap() {
		heap = new ArrayList<Integer>();
		heap.add(null);
	}

	public ArrayList<Integer> getHeap() {
		return heap;
	}

	public void insert(int n) {
		heap.add(n);
		int position = heap.size() - 1;

		while (position > 1 && heap.get(position) < heap.get(position / 2)) {
			int temp = heap.get(position);

			heap.set(position, heap.get(position / 2));
			heap.set(position / 2, temp);

			position /= 2;
		}

	}

	public void delete() {
		if (heap.size() <= 1)
			return;

		heap.set(1, heap.get(heap.size() - 1));
		heap.remove(heap.size() - 1);

		int position = 1;

		while (position * 2 < heap.size() && heap.get(position) > heap.get(position * 2)) {
			int minForIndex = position * 2;

			if (position * 2 + 1 < heap.size() && heap.get(position * 2) > heap.get(position * 2 + 1)) {
				minForIndex = position * 2 + 1;
			}

			int temp = heap.get(position);

			heap.set(position, heap.get(minForIndex));
			heap.set(minForIndex, temp);

			position = minForIndex;
		}



	}
}

• Formation of heap
  • by using ArrayList
    
  • index 0 is not used
    

  private ArrayList<Integer> heap;
  
  public minHeap() {
    heap = new ArrayList<Integer>();
    heap.add(null);
  }
  

• Insertion
  • O(logn)
  • 1^st : simply add the element to the end index
  • 2^nd : constantly compare the element with its parent node and check whether they are satisfied with the condition of heap
  • 3^rd : swap if they are not satisfied
    

  public void insert(int n) {
        heap.add(n);
        int position = heap.size() - 1;
  
        while (position > 1 && heap.get(position) < heap.get(position / 2)) {
            int temp = heap.get(position);
  
            heap.set(position, heap.get(position / 2));
            heap.set(position / 2, temp);
  
            position /= 2;
        }
  
    }
  

• Deletion
  • O(logn)
  • Deletion of heap == remove the root node (index 1)
  • should reconstruct the heap structure after removing the root node
  • 1^st : replace root node’s value with the end node’s value in terms of root node location (and remove the end node)
  • 2^nd : swap for reconstructing the heap structure
    

  public void delete() {
        if (heap.size() <= 1)
            return;
  
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
  
        int position = 1;
  
        while (position * 2 < heap.size() && heap.get(position) > heap.get(position * 2)) {
            int minForIndex = position * 2;
  
            if (position * 2 + 1 < heap.size() && heap.get(position * 2) > heap.get(position * 2 + 1)) {
                minForIndex = position * 2 + 1;
            }
  
            int temp = heap.get(position);
  
            heap.set(position, heap.get(minForIndex));
            heap.set(minForIndex, temp);
  
            position = minForIndex;
        }
  
  
  
    }
  

Use

• Heap Sorting
• Priority Queue
• Solve the Max or Min

Heap With Python

• Use heapq module
  • import heapq
  • implemented for min heap (default)
    

  import heapq
  
  heap = [4, 7, 6, 5, 8, 10, 9]
  heapq.heapify(heap) # sorting list element as min heap
  
  print(heap) # [4, 5, 6, 7, 8, 10, 9]
  
  heapq.heappush(heap, 15)
  
  print(heap) # [4, 7, 6, 5, 8, 10, 9, 15]
  
  print(heapq.heappop(heap)) # 4 (min)
  
  print(heap) # [5, 7, 6, 15, 8, 10, 9]
  
  

  
  

• Max heap
  • Use heapq module and tuple
  • tuple (-i, i) » heapq forms min heap structure based on -i (== max heap based on i)
    
  • Access the element of max heap : heap[i][1]

  import heapq
  
  l = [4, 7, 6, 5, 8, 10, 9]
  heap = []
  
  for i in l:
    heapq.heappush(heap, (-i, i))
  
  print(heap) # [(-10, 10), (-7, 7), (-9, 9), (-4, 4), (-5, 5), (-6, 6), (-8, 8)]