Browse Prior Art Database

Resizeable dynamically allocated heap based priority queues

IP.com Disclosure Number: IPCOM000020111D
Original Publication Date: 2003-Oct-27
Included in the Prior Art Database: 2003-Oct-27
Document File: 3 page(s) / 39K

Publishing Venue

IBM

Abstract

By using a modified pointer based tree it is possible to maintain the same asymptotic characteristics of array based heaps while avoiding some of the problems that make them unsuitable for operating systems use.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Resizeable dynamically allocated heap based priority queues

Heaps have long been a favored method for priority queues because of their scalability and relative simplicity. However, the standard array based implementations are unsuitable for use in operating systems because of the unpredictability of the working set size and the high cost of allocating large arrays.

By using a modified pointer based tree it is possible to maintain the same asymptotic characteristics of array based heaps while avoiding some of the problems that make them unsuitable for operating systems use. The modifications consist of a pointer to the left and right sibling that are used to update a pointer to the last node. The left sibling corresponds to the node that would be immediately left in an array based implementation and the right sibling corresponds to the node that would be immediately to the right in an array based implementation.

By maintaining a last node deletion is facilitated by replacing the node targeted for deletion with the last node. Because deletion is frequent updating the last node needs to be a constant time operation. Without the additional sibling pointers in the pointer based updating the last node pointer would be a lg n operation.

A sample implementation in the C language is included for illustrative purposes.

#include<stdio.h>
#include<stdlib.h>

typedef struct _heapnode* heapnode_ptr_t;

typedef struct _heapnode{
heapnode_ptr_t left_child;
heapnode_ptr_t right_child;
heapnode_ptr_t parent;
heapnode_ptr_t left_sibling;
heapnode_ptr_t right_sibling;
int data;

} _heapnode_t;

heapnode_ptr_t last_node = NULL;
heapnode_ptr_t root_node = NULL;

_dheap_heapify(heapnode_ptr_t branch_root){
int tmp_data;
heapnode_ptr_t smallest;

smallest = branch_root;
while(branch_root->left_child != NULL){
if(branch_root->left_child->data < smallest->data){
smallest = branch_root->left_child;

1

Page 2 of 3

}

if(smallest == branch_root){
return;

}

tmp_data = smallest->data;
smallest-...