title: Data Structures - How to back a heap with a hash table and allow duplicates?
body: <p>I have recently implemented a <strong>min heap</strong>. My heap is not an array based heap. The heap features a method called <code>reduceKey(key, smallerKey)</code> where, given an element, it will change its value to a smaller one and re-adjust the heap accordingly.</p>
  
  <p>In min heaps, finding an element will take O(n) time because the heap structure is unsorted. This would take too long, so I had a friend suggest that I <strong>back my data structure with a hash table</strong>. The HashTable's keys would be the data type of the keys inside the heap and the values would be the actual <em>nodes</em> inside the heap. So, when a user asks, for example, to <code>decreaseKey(22, 10)</code>, it will hash <code>22</code> in the table, find the corresponding node, and decrease it to <code>10</code> in constant time (O(1)). </p>
  
  <p><strong>The problem I'm having:</strong></p>
  
  <p>HashTables do not allow duplicate values; heaps (generally) do. I want my heap to be able to contain duplicate elements. </p>
  
  <p>If I had the situation</p>
  
  <pre><code>h = make Heap
  x = 5
  y = 5
  h.add x
  </code></pre>
  
  <p><code>x</code> is placed into the hash table and is inside of the heap. However, if I attempt to add <code>y</code>, it will hash the same bucket as <code>x</code>. <code>x</code> and <code>y</code> will be compared since they have the same hash code, and since they are exactly the same, <code>y</code> will replace <code>x</code> in the map, ruining my heap structure.</p>
  
  <p><strong>Possible solution</strong></p>
  
  <p>One option I have is to hash elements based on their pointers. For example, <code>x</code> lies at memory address <code>0x0028ff38</code> and <code>y</code> lies at memory address <code>0x0028BA32</code>. They will hash to different values and will not overwrite each other in the map. HOWEVER, the consequences of that would be disastrous, as then the following code would return <code>false</code></p>
  
  <pre><code>h = make heap
  x = 5
  y = 5
  h.add x
  h.contains y # RETURNS FALSE
  </code></pre>
  
  <p>The above code would return false because <code>x</code> and <code>y</code> have different addresses and would hash to different buckets. That doesn't seem right, since the value of <code>5</code> is clearly present inside the heap. <code>contains</code> should return <code>true</code>. Not allowing duplicate values inside the heap feels wrong. </p>
  
  <p>What can be done in this situation?</p>