Range search in a max-heap


I am having trouble with coming up for a suitable algorithm for this question. A max-heap is essentially visualized as a binary tree not a binary search tree. Also the runtime of the algorithm must depend only on the number of elements in the output. I was thinking of doing a preorder traversal on the max heap. While doing the preorder traversal, if the value of a node is less than the given value x, we return to the previous recursive call. All child nodes in a max heap are less than the parent node. Otherwise we output current node and recur on the children.

I am not sure however if the runtime of this algorithm depends only on the number of elements in the output.

Anybody have other suggestions/thoughts? Thanks.

Max-Heap Implementation in Kotlin

I am concerned about a few things about my heap implementation. This is in Kotlin.

For starters-

  • When and when not to use expressions?
  • The round function has an odd behavior it rounds down x.5 to x
  • The use of also to swap numbers

Other suggestions about the algorithm and the code are welcome.

class BinaryHeap : Iterable<Int> {      private val array = mutableListOf(0)     var heapSize = 0      override fun iterator(): Iterator<Int> = array.iterator()      private fun parent(i: Int) = i.shr(1)      private fun left(i: Int) = i.shl(1)      private fun right(i: Int) = i.shl(1).plus(1)      private fun maxHeapify(i: Int) {          var largest: Int         val left = left(i)         val right = right(i)          largest = if (left <= heapSize && array[i] > array[left]) i         else if (left <= heapSize) left         else i          if (right <= heapSize && array[largest] < array[right])             largest = right          if (largest != i) {             swap(largest, i)             maxHeapify(largest)         }      }      val max = if (heapSize != 0) array[1] else -1      fun extractMax(): Int {         return if (heapSize < 1)             -1         else {             val max = array[1]             array[1] = array[heapSize]             heapSize--             maxHeapify(1)             max         }     }      private fun swap(i: Int, j: Int) {         array[i] = array[j].also { array[j] = array[i] }     }      fun insert(i: Int) {         if (array.size > heapSize + 1)             array[++heapSize] = i         else {             array.add(i)             heapSize++         }         var badNode = heapSize         var parentBadNode = parent(badNode)         while (parentBadNode != 0 && array[parentBadNode] < array[badNode]) {             swap(parentBadNode, badNode)             badNode = parentBadNode.also { parentBadNode = parent(parentBadNode) }         }     }      fun insert(i: Iterable<Int>) {         i.forEach {             insert(it)         }     }      override fun toString(): String {         return array.joinToString { "$  it " }     } } ``` 

Heapsort using MaxHeap and MinHeap

As I read in Introduction To Algorithms [3rd edition]:

  1. MaxHeap is used to sort an array into ascending order, while MinHeap is used to sort an array into descending order.

  2. And the tree below can be written in array format as

20 5 10 12 15 8 2 6 2 9

              20         5              10    12    15        8      2  6   2  9 

My question is, why don’t we use it reversely? For example, if we build a MaxHeap from an unordered array, it is already in descending order. It seems redundant to sort again and range it into complete reverse order.

I really appreciate it if anyone can explain this to me.