Return to Question

Finally, my code provides validation. This is intended for testing purposes only, though I'm not sure how this should be exposed to a test project without making Node internal and then exposing the project's internals. Maybe there's no better way.

Finally, my code provides validation. This is intended for testing purposes only, though I'm not sure how this should be exposed to a test project without making Node internal and then exposing the project's internals. Maybe there's no better way.

 /// <summary>
 /// Sets/Replaces node located at child.key in root 
 /// and rebalances the tree if necessary
 /// </summary>
 private Node Set(Node root, Node child)
 {
 if (root == null) return child;
 int cmp = child.Key.CompareTo(root.Key);
 if (cmp == 0)
 return child;
 else if (cmp > 0)
 {
 root.Right = Set(root.Right, child);
 if (root.Right.Priority < root.Priority)
 root = LRotate(root);
 }
 else if (cmp < 0)
 {
 root.Left = Set(root.Left, child);
 if (root.Left.Priority < root.Priority)
 root = RRotate(root);
 }
 return root;
 }
 /// <summary>
 /// Deletes key from root 
 /// and rebalances the tree if necessary
 /// </summary>
 private Node Delete(Node root, TKey key)
 {
 if (root == null) return null;
 int cmp = key.CompareTo(root.Key);
 if (cmp < 0) root.Left = Delete(root.Left, key);
 if (cmp > 0) root.Right = Delete(root.Right, key);
 if (cmp== 0)
 {
 if (root.Left != null && root.Right != null)
 {
 if (root.Left.Priority < root.Right.Priority)
 root = RRotate(root); // it's a min-heap and L < R; promote left
 else
 root = LRotate(root); // it's a min-heap and R < L; promote right
 }
 else if (root.Left != null) root = RRotate(root);
 else if (root.Right != null) root = LRotate(root);
 else return null;
 root = Delete(root, key);
 }
 return root;
 } 

 /// <summary>
 /// Sets/Replaces node located at child.key in root 
 /// and rebalances the tree if necessary
 /// </summary>
 private Node Set(Node root, Node child)
 {
 if (root == null) return child;
 int cmp = child.Key.CompareTo(root.Key);
 if (cmp == 0)
 return child;
 else if (cmp > 0)
 {
 root.Right = Set(root.Right, child);
 if (root.Right.Priority < root.Priority)
 root = LRotate(root);
 }
 else if (cmp < 0)
 {
 root.Left = Set(root.Left, child);
 if (root.Left.Priority < root.Priority)
 root = RRotate(root);
 }
 return root;
 }
 /// <summary>
 /// Deletes key from root by demoting it down to a leaf
 /// and rebalances the tree if necessary
 /// </summary>
 private Node Delete(Node root, TKey key)
 {
 if (root == null) return null;
 int cmp = key.CompareTo(root.Key);
 if (cmp < 0) root.Left = Delete(root.Left, key);
 if (cmp > 0) root.Right = Delete(root.Right, key);
 if (cmp== 0)
 {
 if (root.Left != null && root.Right != null)
 {
 if (root.Left.Priority < root.Right.Priority)
 root = RRotate(root); 
 else
 root = LRotate(root); 
 }
 else if (root.Left != null) root = RRotate(root);
 else if (root.Right != null) root = LRotate(root);
 else return null;
 root = Delete(root, key);
 }
 return root;
 } 

Here is the public wrapper for Delete.

 public void Delete(TKey key)
 {
 root = Delete(root, key);
 }