Differences

This shows you the differences between two versions of the page.

--- algorithm_techniques [2020/08/20 17:17]
paul [Types of Graphs]
+++ algorithm_techniques [2020/10/09 19:39] (current)
@@ Line 92: / Line 92: @@
 {{ ::merge_sort.png?direct&400 |}}
+===== Heaps =====
+Heaps are implemented in C++ as priority_queue.
+See [[https://stackoverflow.com/questions/39514469/argument-for-o1-average-case-complexity-of-heap-insertion|this discussions]].
+Heaps allow us to put data into them and keep track of the mininum or maximum
+value. It does not ordered each individual element.
 ==== Heap Sort ====
@@ Line 270: / Line 279: @@
 {{:pasted:20200816-072543.png?500}}
+==== Iterative Postorder Traversal ====
+You can accomplish a postorder traversal iteratively with two stacks. Here is
+the algorithm:
+<code>
+. Put root in stack 1.
+. While Stack 1 isn't empty
+.   pop top element of stack one and put it in stack 2
+.   put the left and right child of that element in stack 1
+. Print contents of stack 2
+</code>
 ===== Greedy Algorithms =====
@@ Line 452: / Line 475: @@
 === Directed Acyclical Graphs (DAGS) ===
+{{:pasted:20200820-171816.png?500}}
+These graphs don't have any cycles, so you can you explore the whole connected graph without entering a loop.
 ==== Adjacency Lists ====
@@ Line 559: / Line 586: @@
   - Sort input candidates.
   - Make a boolean flag array to track used elements.
-  - Recurse over the canditations, choosing and building a solution, and then unchoosing.
+  - Recurse over the candidates, choosing and building a solution, and then unchoosing.
   - If the next option is the same, skip it.
+===== Loop Detection / Floyd Algo =====