4

I'm implementing a binary heap, and in other languages, it's most convenient to do so by storing an internal array, but set the first element of this array to null and ignore it. This way, if a node is located at index i, its children will always be located at i * 2 and i * 2 + 1.

This no longer works if index 0 is used, because 0 * 2 = 0. However, in Rust, there is no null, so I would have to use Vec<Option<MyHeapItem>> instead of Vec<MyHeapItem>, which makes everything more cumbersome.

So my question is, is there a way to customize Vec<T> so that index 1 refers to the first element?

laptou
  • 6,389
  • 2
  • 28
  • 59
  • 1
    It looks like your question might be answered by the answers of [Is there a way to perform an index access to an instance of a struct?](https://stackoverflow.com/q/28126735/155423) and [How do I implement a trait I don't own for a type I don't own?](https://stackoverflow.com/q/25413201/155423). If not, please **[edit]** your question to explain the differences. Otherwise, we can mark this question as already answered. – Shepmaster Aug 14 '19 at 17:41
  • @Shepmaster Thanks, this did answer my question. – laptou Aug 14 '19 at 17:43
  • 5
    You can just also `i * 2 + 1` and `i * 2 + 2` instead for the child indices? – Zeta Aug 14 '19 at 17:43
  • @Zeta oops, maybe I didn't get enough sleep last night – laptou Aug 14 '19 at 17:47
  • 3
    For future searchers, explicitly stating the fusion of the two duplicates: No, you cannot change how a `Vec` is indexed, but you can create a *newtype* around a `Vec` and implement `Index` / `IndexMut` for that type however you'd like. – Shepmaster Aug 14 '19 at 17:49
  • @laptou I accidentally a word in my comment too, so I probably didn't get enough sleep last night either... :D – Zeta Aug 14 '19 at 17:49

0 Answers0