README
¶
Binary Heap
## Data Structure
A binary heap is a heap data structure created using a binary tree.
Binary heap has two rules:
- Shape property: Binary Heap has to be complete binary tree at all levels except the last level.
- Heap property: All nodes are either greater than equal to (Max-Heap) or less than equal to (Min-Heap) to each of its child nodes.
Implementation:
- Use array to store the data.
- Start storing from index 1, not 0.
- For any given node at position
[i]:- its Left Child is at
[2*i]if available. - its Right Child is at
[2*i+1]if available. - its Parent Node is at
[i/2]if available.
- its Left Child is at
## Heap Operations
Insert
- Add the element at the bottom leaf of the Heap.
- Perform the Bubble-Up operation: ~ O(log n)
- Bubble-Up a.k.a up-heap, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up
- If inserted element is smaller than its parent node in case of Min-Heap OR greater than its parent node in case of Max-Heap, swap the element with its parent.
- Keep repeating the above step, if node reaches its correct position, STOP.
Extract-Min OR Extract-Max Operation
- Take out the element from the root.( it will be minimum in case of Min-Heap and maximum in case of Max-Heap).
- Take out the last element from the last level from the heap and replace the root with the element.
- Perform Sink-Down
Delete
- Find the index for the element to be deleted.
- Take out the last element from the last level from the heap and replace the index with this element.
- Perform Sink-Down operation: ~ O(log n)
- If replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child (Min-Heap) or with its greatest child (Max-Heap).
- Keep repeating the above step, if node reaches its correct position, STOP.
See http://algorithms.tutorialhorizon.com/binary-min-max-heap/
Documentation
¶
Index ¶
- type Heap
- type Item
- type IxHeap
- func (h *IxHeap) Add(i int)
- func (h *IxHeap) Delete(item int) int
- func (h *IxHeap) DeleteAt(k int) int
- func (h *IxHeap) ExtractMax() int
- func (h *IxHeap) ExtractMin() int
- func (h *IxHeap) GetSize() int
- func (h *IxHeap) IsEmpty() bool
- func (h *IxHeap) PeekMax() (int, error)
- func (h *IxHeap) PeekMin() (int, error)
- func (h *IxHeap) String() string
- type MinIntHeap
- type PriorityQueue
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap []*Item
Heap is a list of *Item
func (*Heap) ExtractMax ¶
ExtractMax removes the maximum item from heap
func (*Heap) ExtractMin ¶
ExtractMin removes the minimum item from heap
type IxHeap ¶
type IxHeap struct {
// contains filtered or unexported fields
}
IxHeap struct
type MinIntHeap ¶
type MinIntHeap []int64
MinIntHeap is a min-heap of integers. - Construction : h := &MinIntHeap{3, 1, 4} - Initialization: heap.Init(h) // sink down from half to top - Add an integer: heap.Push(h, 5) // call heap.Interface.Push then bubble up - Other mehotds : heap.Pop(h), heap.Fix(h, 3) - Peek min/max : (*h)[0], (*h)[len(*h)-1]
func (*MinIntHeap) ExtractMax ¶
func (mih *MinIntHeap) ExtractMax() int64
ExtractMax removes the maximum item from heap
func (*MinIntHeap) ExtractMin ¶
func (mih *MinIntHeap) ExtractMin() int64
ExtractMin removes the minimum item from heap
func (*MinIntHeap) Len ¶
func (mih *MinIntHeap) Len() int
Len implements sort.Interface in heap.Interface
func (*MinIntHeap) Less ¶
func (mih *MinIntHeap) Less(i, j int) bool
Les implements sort.Interface in heap.Interface
func (*MinIntHeap) Swap ¶
func (mih *MinIntHeap) Swap(i, j int)
Swap implements sort.Interface in heap.Interface
type PriorityQueue ¶
type PriorityQueue []*Item
PriorityQueue is a list of *Item
func (PriorityQueue) Len ¶
func (pq PriorityQueue) Len() int
Len implements sort.Interface in heap.Interface
func (PriorityQueue) Less ¶
func (pq PriorityQueue) Less(x, y int) bool
Less implements sort.Interface in heap.Interface
func (*PriorityQueue) Pop ¶
func (pq *PriorityQueue) Pop() interface{}
Pop implements heap.Interface
func (*PriorityQueue) Push ¶
func (pq *PriorityQueue) Push(x interface{})
Push implements heap.Interface
func (PriorityQueue) Swap ¶
func (pq PriorityQueue) Swap(x, y int)
Swap implements sort.Interface in heap.Interface
Source Files