> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/19.-heaps-and-priority-queues/19.3-pq-implementation.md).

# 19.3 PQ Implementation

The actual implementation, which we will use and the book uses, is quite similar to the representation we discussed at the end of the previous chapter. The one difference is that we will leave one empty spot at the beginning of the array to simplify computation.

* `leftChild(k)`= $$k \* 2$$
* `rightChild(k)`= $$k \* 2 + 1$$
* `parent(k)`= $$k / 2$$

### Comparing to alternative implementations <a href="#comparing-to-alternative-implementations" id="comparing-to-alternative-implementations"></a>

| Methods          | Ordered Array | Bushy BST   | Hash Table | Heap        |
| ---------------- | ------------- | ----------- | ---------- | ----------- |
| `add`            | $$Θ(N)$$      | $$Θ(logN)$$ | $$Θ(1)$$   | $$Θ(logN)$$ |
| `getSmallest`    | $$Θ(1)$$      | $$Θ(logN)$$ | $$Θ(N)$$   | $$Θ(1)$$    |
| `removeSmallest` | $$Θ(N)$$      | $$Θ(logN)$$ | $$Θ(N)$$   | $$Θ(logN)$$ |

Awesome! We can see that we have improved our runtime and we have also solved the problem of duplicate elements. Couple notes:

* Heap operations are **amortized** analysis, since the array will have to resize (not a big deal)
* BST's can have constant time `getSmallest` if pointer is stored to smallest element
* Array-based heaps take around 1/3rd the memory it takes to represent a heap using approach 1A (direct pointers to children)

**Exercise 13.3.1** Some lingering implementation questions:

1. How will the PQ know how to order the items? Say we had a PQ of dogs, would it order by weight or breed?
2. Is there a way to allow for a flexibility of orderings?
3. What could we do to make a MinPQ into a MaxPQ?


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/19.-heaps-and-priority-queues/19.3-pq-implementation.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `build a script that syncs our docs to a CMS` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.