Basic Storage of Heap
Concept and introduction
Heap is a general term for a special class of data structures in computer science.
A heap is usually an array object that can be viewed as a complete binary tree.
A heap satisfies the following properties:
- The value of a node in a heap is always no greater than or no less than the value of its parent node.
- A heap is always a complete binary tree.
II. Applicability Notes
A heap uses the structure of a complete binary tree to maintain a set of data, and then performs related operations. The time complexity of a typical operation isO(1)~O(logn)Meanwhile, heaps are commonly used for dynamically allocating and releasing objects used by programs.
For a priority queue usage scenario, with a regular array or an ordered array, the worst case isO(n^2)the heap data structure can also improve the efficiency of enqueue and dequeue operations.
| Enqueue | Dequeue | |
|---|---|---|
| Normal array | O(1) | O(n) |
| Ordered array | O(n) | O(1) |
| Heap | O(logn) | O(log) |
III. Structure Diagram
A binary heap is a complete binary tree, and the value of a node in the heap is always no greater than the value of its parent node. The depth of the complete binary tree is k. Except for the k-th level, the number of nodes in all other levels (1 to k-1) reaches the maximum, and all nodes at the k-th level are continuously concentrated on the leftmost side.
The heap whose root node is the largest is called a max heap, as shown in the figure below:
We can use an array to store the binary heap; the labels on the right are the indices of the array.
Assuming the index position of the current element is i, we can derive the rule:
parent(i) = i/2（取整） left child(i) = 2*i right child(i) = 2*i +1
IV. Java Example Code
Source Code Package Download:Download
src/example/heap/MaxHeap.java file code:
/**
* Heap Definition
*/
public class MaxHeap<T> {
private T[] data;
private int count;
// Constructor, constructs an empty heap that can hold capacity elements
public MaxHeap(int capacity){
data = (T[])new Object[capacity+1];
count = 0;
}
// Return the number of elements in the heap
public int size(){
return count;
}
// Return a boolean indicating whether the heap is empty
public boolean isEmpty(){
return count == 0;
}
// Test MaxHeap
public static void main(String[] args) {
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
System.out.println(maxHeap.size());
}
}