526互联

Heap

发布时间 2023-10-24 10:29:28作者: HardisonDream
dg-publish: true

study/datastructure

A Heap is a complete binary tree, where all levels of tree, except
Possibly the last level, are fully filled

![[Pasted image 20231023104516.png|300]]

Min Heap

  • A parent node has a key that is smaller than its child nodes
  • The root node has the smallest key

![[Pasted image 20231023104907.png|300]]

Common Operations

  • Get the element with the minimum or maximum key
  • Remove the element with the minimum or maximum key
  • Insert a new element

Applications

  • Priority Queues (e.g. CPU job-scheduling)
  • Sorting (via HeapSort)

Implementation

Use an array to represent a Min Heap
![[Pasted image 20231023110447.png|300]]

![[Pasted image 20231023110228.png|300]]

i=index of array
Parent node : i
	Left node: 2*i+1
	Right node: 2*i+2
Find a node's parents; (i-1)/2

Insert

Place new element 0 at the end of Heap
![[Pasted image 20231023132640.png]]

Compare new element 0 with parent element 4;swap as new element 0 is smaller
![[Pasted image 20231023132758.png]]

Swap new element 0 with parent element 1 as new element is smaller;stop as heap property is restored
![[Pasted image 20231023132941.png]]

Remove

Replace root element 1 with last element 5
![[Pasted image 20231023133035.png]]

Child element 2 is the smallest,sqap with target element 5
![[Pasted image 20231023133128.png]]

Child element 3 is the smallest,swap with target element 5; stop as heap property is restored
![[Pasted image 20231023133142.png]]

Heap Sort

  • Given a list of inputs, how to sort its key in ascending order?
    • Construct a Min Heap using the inputs
    • While Min Heap not empty
      • Extract the minimum key