MinMax Heap implementation without an array

I found lots of MinMax Heap implementations, that were storing data in an array. It is realy easy to implement, that is way I am looking for something different. I want to create a MinMax Heap using only elements of the Heap with pointers to left child and right child (and afcourse a key to compare).开发者_运维百科 So the Heap have only pointer to the root object (min level), and a root object have a pointer to his children (max level) and so on. I know how to insert a new object (finding a proper path by using binary represenation of int depending on Heap size), but I don't know how to implement the rest (push up (down) the element, find parent or grandparent).

Thx for help

A priority queue using a heap ordered binary tree can be implemented using a triply linked list structure instead of an array. you will need three links per node:two to traverse down and one to traverse up.

The heapq module source code shows to implement the steps for pushing up and down. To switch from an array implementation to a pointer implementation, replace the arr[2*n+1] computation with node.left and arr[2*n+2] with node.right. For parent references such as arr[(n-1)>>1], every node will need a pointer to its parent, node.parent.

Alternatively, you can adopt a functional style which makes this all very easy to implement. I found the code for treaps implemented in Lisp to be an inspiration for how to do this.

I have solved this problem as part of an assignment long back. You can find it here

I have multiple implementations in Java and C++ implementing MinHeap with and without arrays. See my Java implementations for the solution. And yes it is very much possible to implement Heap without arrays. You just have to remember where to insert the next node and how to heapify and reverse heapify.

Edit1: I also tried to look up any existing solutions for min heap without arrays but couldn't find any. So, I am posting it here so it could be helpful for anyone who wishes to know the approach.

Yes, you can implement it without relying on an array. I personally relied on a binary counter... Here is my implementation(https://github.com/mohamedadnane8/HeapsUsingPointers) in c. Note that this is still a very fast implementation with log(n).

                1 => binary "1"
            2=> "10"            3=> "11"
4=>  "100"      5= "101"     6="110"        7="111"

In this program i tried to use the sequence of numbers to insert and delete as u can see above the tree can be easily represented as binary strings of numbers. The first '1' in the binary string is to start. After that the sequence of 0 and 1 determines where to go '1' means go to the left and '0' go to the right.

Also, note that this implementation relies on a very small array of characters or integers that make the calculation of the binary numbers faster but u can rely on bin() function to convert ur counter to a binary number(I implemented the array just to practice a bit my problem-solving skills). Sorry if I couldn't explain it very well, I lack a bit in my communication skills.

It is hard implement binary heap without array. Because you should keep all the parent while inserting you pass and then do operation push up and down. like that [parent_1, parent_2 ... parant_k] and then if parent_(k+1) < parant_k pushUp and rearrange their right child and left child