DSA prefi

heap - is a complete binary tree where the value of each of each parent node is either higher or lower than the value of its child nodes.

These are the two (2) types of heap:

o Min Heap – The value of each parent node is less than or equal to the values of its child nodes.

o Max Heap – The value of each parent node is greaterthan or equal to the values of its child nodes.

• Heaps can be implemented in Java using ArrayList from the java.util package.

Example:

ArrayList<Integer> heap = new ArrayList<>();

addAll() method - To create a heap with initial values of the Collections class (also from the java.util package).

Priority Queues - A priority queue is a special type of queue where elements are processed based on their order (natural or custom).

• Priority queues can be implemented in Java using the PriorityQueue class from the java.util package.

Example:

PriorityQueue<Integer> printer = new PriorityQueue<>();

To enqueue - use add() or offer().

To dequeue - use poll() or remove().

Comparator - is used to create a specific ordering for a collection of objects.

• To create a comparator in Java, use the Comparator interface

and its methods such as comparing(), comparingInt(), and compare().

• Sample code to dequeue in Java based on a custom order:

Comparator<String> comp = Comparator.comparing(String::length);

Sets - A set is a collection of elements where each element is unique.

• Common set operations:

o Union: The union of two (2) sets (A ∪ B) is the set that contains all the elements in either set.

o Intersection: The intersection of two (2) sets (A ∩ B) is the set that contains only the elements common to both sets.

o Difference: The difference of sets A and B (A – B) is the set that contains the elements that are in A but not in B.

o Subset: Set A is a subset of set B (A ⊂ B) if every element of set A is also an element of set B.

• Java contains three (3) general-purpose set implementations. All are included in the java.util package.

o HashSet – This stores its elements in a hash table without a guaranteed order upon iteration. This is the best-performing implementation.

o TreeSet – This stores its elements in a special type of tree where elements are sorted (natural or custom) during iteration.

o LinkedHashSet – This stores its elements in a hash table with a linked list running through it. The order of the elements during the iteration is the same as the order they were inserted into the set.

• Sample codes for sets in Java:

1. To create an empty set:

Set a = new HashSet();

Set b = new TreeSet ();

Set c = new LinkedHashSet();

2. To add items to the set:

Collections.addAll(a, "Mark", "Nika", "Mairo", "Kae");

3. To determine the union, intersection, and difference:

union.containsAll()

intersection.retainAll()

difference.removeAll()

4. To determine whether a set is a subset of another set:

System.out.println(a.containsAll(b));

• Curly braces or the set() function can be used to implement sets in Python.

• Sample codes for sets in Python:

1. To create an empty set:

a = set()

2. To initialize a set:

a = set(["Mark", "Nika", "Mairo", "Kae"])

b = {"John", "Marco", "Mark"}

3. To determine the union, intersection, and difference:

union = a|b

intersection = a&b

difference = a - b

4. To determine whether a set is a subset of another set:

print(a.issubset(b))

Maps

• A map is a set of ordered pairs where elements are known as keys (identifiers) and values (content).

o A map cannot contain duplicate keys.

o Each key can map to only one (1) value.

• Same with sets, there are also three (3) general-purpose map implementations in Java: HashMap, TreeMap, and LinkedHashMap.

• Sample codes for maps in Java:

1. To create an empty map:

Map <String, String> nameMap = new HashMap<>();

2. To insert a mapping:

nameMap.put("M1", "Mark");

nameMap.put("M2", "Mairo");

3. To delete the mapping for a key:

nameMap.remove("M2");

4. To replace a key’s value:

nameMap.replace("M2", "Marco");

5. To retrieve the value based on the key:

System.out.println(nameMap.get("M1"));

6. To check whether a map contains a mapping for the

specified key or value:

System.out.println(nameMap.containsKey("M2"));

System.out.println(nameMap.containsValue("Mark"));

7. To retrieve all the keys and values of a map:

System.out.println(nameMap.keySet());

System.out.println(nameMap.values());

8. To display entries in separate lines:

for (Map.Entry e : nameMap.entrySet()) {

System.out.println(e.getKey() + ": " +

e.getValue());

• Maps in Python are known as dictionaries. To create a dictionary, use the colon symbol (:) for key-value pairs within the curly braces.

• Sample codes for dictionaries in Python:

1. To create an empty dictionary:

name_map = { }

2. To initialize a dictionary:

name_map = {"M1": "Mark", "M2": "Mairo"}

3. To insert a mapping:

name_map["N"] = "Nika"

4. To delete the mapping for a key:

del name_map["M2"]

5. To replace a key’s value:

name_map["M2"] = "Marco"

6. To retrieve the value based on the key:

print(name_map["M1"])

7. To check whether a dictionary contains a mapping for the specified key:

print("M2" in name_map)

8. To retrieve all the keys and values of a dictionary:

print(list(name_map))

print(list(name_map.values()))

9. To display entries in separate lines:

for x, y in name_map.items():

print(x, y)