Heap
A heap is an unsorted data structure that organizes nodes in a hierarchical tree.
In a
max-heap, the values of a parent node are always greater than the values
of its child nodes. In a
min-heap, the values of a parent node are always less than
the values of its child nodes.
A heap is a maximally efficient implementation of a priority queue. A priority
queue serves elements according to their priority and
falls back to a FIFO policy
for identical priorities. The PriorityQueue class uses an object array to store
its values. Although heaps are visually represented as a tree, they can
be compactly stored inside of an array and nodes
can be located by index
arithmetic. PriorityQueue is not thread-safe,
but PriorityBlockingQueue is a thread-safe alternative.
Set
A Set is a data structure that holds a collection of unique values. Sets often
delegate functionality to maps because the keys in a map are already unique.
HashSet
utilizes a HashMap, which does not
maintain the insertion order
of its elements. LinkedHashSet utilizes a LinkedHashMap,
which maintains insertion order by way of an auxiliary LinkedList.
TreeSet
utilizes a TreeMap, which maintains the natural ordering of its
elements. None of
these classes are thread-safe, but the
Collections#newSetFromMap()
method can create a set out
of a ConcurrentHashMap.
Questions
What is the difference between an ArrayList and a LinkedList?
How does a HashMap work internally?
What would happen if a key’s hashCode() or equals() method was incorrect?
What is the difference between a stack and a queue?
What is the difference
between a binary search tree, red-black tree, and a heap?
What is the difference between a HashSet, LinkedHashSet, and TreeSet?
What is the difference between a fail-fast iterator and a fail-safe iterator?